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?

 

解法一：递归

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector
     
       preorderTraversal(TreeNode* root) {        vector
      
        ret;        Helper(ret, root);        return ret;    }    void Helper(vector
       
        & ret, TreeNode* root)    {        if(root)        {            ret.push_back(root->val);            Helper(ret, root->left);            Helper(ret, root->right);        }    }};
       
      
     

 

解法二：借助栈的非递归，需要记录每个节点是否访问过

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector
     
       preorderTraversal(TreeNode *root) {        vector
      
        ret;        if(root == NULL)            return ret;        stack
       
         stk;        unordered_map
        
          visited;        stk.push(root);        visited[root] = true;        while(!stk.empty())        {            TreeNode* top = stk.top();            stk.pop();            ret.push_back(top->val);            if(top->right != NULL && visited[top->right] == false)            {                stk.push(top->right);                visited[top->right] = true;            }            if(top->left != NULL && visited[top->left] == false)            {                stk.push(top->left);                visited[top->left] = true;            }        }        return ret;    }};
        
       
      
     

 

解法三：借助栈的非递归，无需记录每个节点是否访问过。

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector
     
       preorderTraversal(TreeNode* root) {        vector
      
        ret;        if(root == NULL)            return ret;        stack
       
         stk;        stk.push(root);        while(!stk.empty())        {            TreeNode* top = stk.top();            stk.pop();            ret.push_back(top->val);            if(top->right)                stk.push(top->right);            if(top->left)                stk.push(top->left);        }        return ret;    }};