# Binary Tree Postorder Traversal

Iterative

<http://www.jianshu.com/p/456af5480cee>

先走到左子树底，此时此Node已无左子树，看看是否有右子树，没有或者已经visit过，就可以输出了。有的话转入右子树继续遍历。所以需要lastVisited标记。

一直走到左边底端的代码一直错，要注意，直接比较cur和加cur，不是cur.left！

```
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<Integer>();
        if(root == null)
        return ret;
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode cur = root;        
        TreeNode lastVisit = cur;

        while(cur != null || !s.isEmpty()){
            while(cur != null){
                s.push(cur);
                cur = cur.left;
            }
            cur = s.peek();
            //如果右子树不存在或者已经访问，直接输出
            if(cur.right == null || cur.right == lastVisit){
                s.pop();
                ret.add(cur.val);
                lastVisit = cur;
                cur = null;//此处联想right都遍历过了，无处可去所以cur=null
            }else{
                cur = cur.right;//否则转入右子树继续
            }

        }
        return ret;
    }
```

Recursive

```
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<Integer>();
        if(root == null)
        return ret;
        List<Integer> left = postorderTraversal(root.left);
        List<Integer> right = postorderTraversal(root.right);
        ret.addAll(left);
        ret.addAll(right);
        ret.add(root.val);

        return ret;
    }
```

另一种解法是使用两个栈。试着在纸上写一下代码。我认为这种解法非常的神奇而优美。你可能觉得这很不可思议，但实际上它做的是反向的先序遍历。亦即遍历的顺序是：节点 ->右子树 ->左子树。这生成的是后根遍历的逆序输出。使用第二个栈，再执行一次反向输出即可得到所要的结果。其实第一个栈就是前序遍历的栈实现，只是先右后左而已，然后栈再倒一次。

C++

```
void postOrderTraversalIterativeTwoStacks(BinaryTree *root) { 
    if (!root) return; 
    stack<BinaryTree*> s; 
    stack<BinaryTree*> output; 
    s.push(root); 
    while (!s.empty()) 
        { 
            BinaryTree *curr= s.top(); 
            output.push(curr); 
            s.pop(); 
            if (curr->left) s.push(curr->left); 
            if (curr->right) s.push(curr->right); 
        } 
    while (!output.empty()) 
        { 
            cout << output.top()->data << " ";
            output.pop();
        }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/l3er-cha-shu-he-fen-zhi-fa/binary-tree-postorder-traversal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.