Binary Tree Postorder Traversal

LeetCode #145

Description:

Example:

Note

Idea:

这个Iteration的太复杂了，记不住....

Code:

Iteration version

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        TreeNode *p, *q;

        stack<TreeNode *> stack_node;
        p=root;

        do{
            while(p != NULL){  /* 往左下走 */
                stack_node.push(p);
                p = p->left;
            }
            q=NULL;
            while(!stack_node.empty()){
                p=stack_node.top();
                stack_node.pop();
                if(p->right==q){ /* 右孩子不存在或已被访问，访问之 */
                    result.push_back(p->val);
                    q=p;  /* 保存刚访问过的结点 */
                }
                else{ /* 当前结点不能访问，需第二次进栈 */
                    stack_node.push(p);
                    p=p->right; /* 先处理右子树 */
                    break;
                }
            }
        } while(!stack_node.empty());

        return result;

    }

};

Recursion version

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;

        RecursionPostorder(root, result);
        return result;
    }

    void RecursionPostorder(TreeNode* root, vector<int> &result){
        if(root==NULL) return;

        RecursionPostorder(root->left, result);
        RecursionPostorder(root->right, result);
        result.push_back(root->val);
    }
};