145. Binary Tree Postorder Traversal.md

title	toc	date	tags	top
145. Binary Tree Postorder Traversal	false	2017-10-30	Leetcode Stack Tree	145

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) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        if (cur != null) {
            list.add(0, cur.val);
            stack.push(cur.left);
            stack.push(cur.right); 
        }
    }
    return list;
}