1
2
3
4
5
6
7
8
9
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

Iterative:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null) return res;
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while (!st.empty()) {
            TreeNode node = st.pop();
            res.addFirst(node.val);
            if (node.left != null) st.push(node.left);
            if (node.right != null) st.push(node.right);
        }
        return res;
    }
}

本来:

如果preorder, 是先pushnode.right再node.left, 从stack拿出来是先入后出那么是left再right, “左右根”, good;

但是这里是postorder, 所以用的addFirst(), 是每次往linkedlist最前面加节点, 此时如果先pushnode.right再node.left,往外拿是“先left再right”，因为是从前面加的，所以变成了“右左根”，而如果就是先pushnode.left再node.right, 那么从栈拿出来是先右再左，addFirst()从前面加刚好就是“左右根”

相当于就是addFirst和stack都是相反的操作所以往栈push的时候先左后右。

骚操作。

mundane recursive:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        pre(root, res);
        return res;
    }
    public void pre(TreeNode node, List<Integer> res) {
        if (node == null) return;
        pre(node.left, res);
        pre(node.right, res);
        res.add(node.val);
    }
}