EEPW论坛

Given a binary tree, return the preordertraversal 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?

1. class Solution  

2. {  

3. public:  

4.     vector<int> preorderTraversal(TreeNode* root)  

5.     {  

6.         vector<int> res;  

7.         if (!root)  

8.         {  

9.             return res;  

10.         }  

11.   

12.         stack<TreeNode*> st;  

13.         st.push(root);  

14.           

15.         while (st.size())  

16.         {  

17.             TreeNode* tmp = st.top();  

18.             st.pop();  

19.   

20.             res.push_back(tmp->val);  

21.             if (tmp->right)  

22.             {  

23.                 st.push(tmp->right);  

24.             }  

25.             if (tmp->left)  

26.             {  

27.                 st.push(tmp->left);  

28.             }  

29.         }  

30.         return res;  

31.     }  

32. };  

1. class Solution  

2. {  

3. public:  

4.     vector<int> preorderTraversal(TreeNode* root)  

5.     {  

6.         vector<int> ans;  

7.         LRD(ans, root);  

8.         return ans;  

9.     }  

10.   

11.     void LRD(vector<int>&ans, TreeNode* root)  

12.     {  

13.         if (root==NULL)  

14.         {  

15.             return;  

16.         }  

17.   

18.         ans.push_back(root->val);  

19.         LRD(ans, root->left);  

20.         LRD(ans, root->right);  

21.           

22.     }  

23. };