[LintCode] 472 Binary Tree Path Sum III 解题报告

Description
Give a binary tree, and a target number, find all path that the sum of nodes equal to target, the path could be start and end at any node in the tree.



Example
Given binary tree:

    1
   / \
  2   3
 /
4
and target = 6. Return :

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



思路
现在的题意是可以从任何一点出发，而且有parent节点。
那么我们其实是traverse一遍这棵树，在每一点，我们出发找有没有符合条件的路径。
在每一点我们可以有三个方向：左边，右边，和上面。但是我们需要避免回头，所以需要一个from节点的参数。




Code

/**
 * Definition of ParentTreeNode:
 * 
 * class ParentTreeNode {
 *     public int val;
 *     public ParentTreeNode parent, left, right;
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    public List<List<Integer>> binaryTreePathSum3(ParentTreeNode root, int target) {
        // Write your code here
        
        List<List<Integer>> result = new ArrayList<>();
        helper(root, result, target);
        return result;
    }
    
    public void helper(ParentTreeNode root, List<List<Integer>> result, int target) {
        
        if (root == null) {
            return;
        }
        
        List<Integer> path = new ArrayList<>();
        findSum(root, null, result, path, target);
        
        helper(root.left, result, target);
        helper(root.right, result, target);
    }
    
    public void findSum(ParentTreeNode root, 
                        ParentTreeNode from, 
                        List<List<Integer>> result, 
                        List<Integer> path, 
                        int target) {
        
        if (root == null) {
            return;
        }
        
        path.add(root.val);
        target -= root.val;
        
        if (target == 0) {
            result.add(new ArrayList<>(path));
        }
        
        if (root.parent != null && root.parent != from) {
            findSum(root.parent, root, result, path, target);
        }
        
        if (root.left != null && root.left != from) {
            findSum(root.left, root, result, path, target);
        }
        
        if (root.right != null && root.right != from) {
            findSum(root.right, root, result, path, target);
        }
        
        path.remove(path.size() - 1);
    }
}