Binary Tree Postorder Traversal

Given a binary tree, return the postorder 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  * 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
     
       postorderTraversal(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             traversal(root->left,ret);22             traversal(root->right,ret);23             ret.push_back(root->val);24         }25     }26 };