LeetCode144—Binary Tree Preorder Traversal

布满荆棘的人生 2022-07-16 04:22 108阅读 0赞

## 原题 ##

[原题链接][Link 1]

> 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?

## 分析 ##

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

//递归
    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;
        }
    };

[Link 1]: https://leetcode.com/problems/binary-tree-preorder-traversal/
[Link 2]: http://blog.csdn.net/zhangxiao93/article/details/52734630