145.Binary Tree Postorder Traversal

485 查看

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

For example:
Given binary tree {1,#,2,3},
1

\
 2
/

3
return [3,2,1].

解答:
最主要的思想是先存root的话,整个存储的顺序会变反,所以要插入存储进去。
1.Iterative解答:

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        
        if (root == null) return result;
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(0, node.val);
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return result;
    }
}

2.Recursive解答:

//Recursive
public void Helper(TreeNode root, List<Integer> result) {
    if (root == null) return;
    result.add(0, root.val);
    Helper(root.right, result);
    Helper(root.left, result);
}

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