EEPW论坛

Given a binary tree, return thepostorder traversal of its nodes' values.

For example:
Given binary tree{1,#,2,3},

   1
    \
     2
    /
   3

return[3,2,1].

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

方法一：

（1）前序遍历：根-》左-》右

（2）变成：根-》右-》左

（3）然后逆序

1. class Solution  

2. {  

3. public:  

4.     vector<int> postorderTraversal(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->left)  

22.             {  

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

24.             }  

25.             if (tmp->right)  

26.             {  

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

28.             }  

29.         }  

30.   

31.         reverse(res.begin(), res.end());  

32.     }  

33. };  

方法二：递归实现

1. class Solution  

2. {  

3. public:  

4.     vector<int> postorderTraversal(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.         LRD(ans, root->left);  

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

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

21.     }  

22. };