LeetCode OJ：Binary Tree Postorder Traversal（后序遍历二叉树）

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

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

return [3,2,1].

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

Subscribe to see which companies asked this question
递归当然很容易实现拉，但是要求是不使用递归来实现，先贴一个递归的代码：

 1 class Solution {
 2 public:
 3     vector<int> postorderTraversal(TreeNode* root) {
 4         if(!root) return ret;
 5         tranverse(root);
 6         return ret;
 7     }
 8 
 9     void tranverse(TreeNode * root)
10     {
11         if(!root) return;
12         tranverse(root->left);
13         tranverse(root->right);
14         ret.push_back(root->val);
15     }
16 private:
17     vector<int> ret;
18 };

下面是非递归实现的代码，用一个栈来保存数据：
注意左右子树的压栈顺序

 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<int> postorderTraversal(TreeNode* root) {
13         vector<int> ret;
14         if(!root) return ret;
15         stack<TreeNode *> s;
16         s.push(root);
17         while(!s.empty()){
18             TreeNode * t = s.top();
19             if(!t->left && !t->right){
20                 ret.push_back(t->val);
21                 s.pop();
22                 continue;
23             }
24             if(t->right){
25                 s.push(t->right);
26                 t->right = NULL;
27             }
28             if(t->left){
29                 s.push(t->left);
30                 t->left = NULL;
31             }
32         }
33         return ret;
34     }
35 };