145. Binary Tree Postorder Traversal

Leetcode Stack Tree

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

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

分析

这道题目和144. Binary Tree Preorder Traversal一摸一样，给出三种方案：

有帮助函数的递归，省去了反复要生成List<Integer>.

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    postorderTraversalHelper(root, list);
    return list;
}

private void postorderTraversalHelper(TreeNode root, List<Integer> list) {
    if (root == null) return;
    postorderTraversalHelper(root.left, list);
    postorderTraversalHelper(root.right, list);
    list.add(root.val);
}

直接递归:

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

迭代:

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> list = new LinkedList<>();
    if (root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode next = stack.pop();
        if (next.left != null) stack.push(next.left);
        if (next.right != null) stack.push(next.right);
        list.addFirst(next.val);
    }
    return list;
}