246.Binary Tree Path Sum II

1.Description(Easy)

Your are given a binary tree in which each node contains a value. Design an algorithm to get all paths which sum to a given value. The path does not need to start or end at the root or a leaf, but it must go in a straight line down.

Example

Given a binary tree:

    1
   / \
  2   3
 /   /
4   2

for target =6, return

[
  [2, 4],
  [1, 3, 2]
]

2.Code

Version 1:Recursive

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

Version 2: Iterative