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?

 

不算难，使用stack即可。

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     vector
     
       preorderTraversal(TreeNode* root) {13         vector
      
        result;14         TreeNode* p;15         stack
       
         mystack;16         p = root;17         if(p) mystack.push(p);18         while(!mystack.empty())19         {20             p = mystack.top();21             mystack.pop();22             result.push_back(p->val);23             if(p->right) mystack.push(p->right);24             if(p->left) mystack.push(p->left);25         }26         return result;27     }28 };
       
      
     

 递归的方法很统一。先序，中序，后续，只要修改遍历的顺序即可。

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     vector
     
       preorderTraversal(TreeNode* root) {13         vector
      
        result;14         traversal(root,result);15         return result;16     }17     void traversal(TreeNode* root,vector
       
        & ret)18     {19         if(root)20         {21             ret.push_back(root->val);22             traversal(root->left,ret);23             traversal(root->right,ret);24         }25     }26 };