LeetCode144—Binary Tree Preorder Traversal-蒲公英云

LeetCode144—Binary Tree Preorder Traversal

原题

原题链接

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

分析

很明显是考虑先序遍历的非递归写法，不过递归也能过。
参见：二叉树的遍历

//递归
class Solution {
private:
    void preOrder(TreeNode*root,vector<int>&res)
    {
        if(root==NULL)
            return;
        res.push_back(root->val);
        preOrder(root->left,res);
        preOrder(root->right,res);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>res;
        preOrder(root,res);
        return res;
    }
};
//迭代
class Solution {
private:
    stack<TreeNode*>mystack;
    void preOrder(TreeNode*root,vector<int>&res)
    {
      TreeNode *p =root;
      while(p!=NULL||!mystack.empty())
      {
          while(p!=NULL)
          {
              res.push_back(p->val);
              mystack.push(p);
              p=p->left;
          }
          if(!mystack.empty())
          {
              p=mystack.top();
              mystack.pop();
              p=p->right;
          }
      }
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>res;
        preOrder(root,res);
        return res;
    }
};