Binary Tree With Parent Node

Lowest Common Ancestor II: http://lintcode.com/en/problem/lowest-common-ancestor-ii/

/**
 * Definition of ParentTreeNode:
 * 
 * class ParentTreeNode {
 *     public ParentTreeNode parent, left, right;
 * }
 */
public class Solution {
    /**
     * @param root: The root of the tree
     * @param A, B: Two node in the tree
     * @return: The lowest common ancestor of A and B
     */
    public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
                                                 ParentTreeNode A,
                                                 ParentTreeNode B) {
        // Write your code here   
        ParentTreeNode lowestAncester = null;
        List<ParentTreeNode> pathA = getPathToRoot(A);
        List<ParentTreeNode> pathB = getPathToRoot(B);

        int i = pathA.size() - 1, j = pathB.size() - 1;
        while(i >= 0 && j >= 0){
            if(pathA.get(i) != pathB.get(j)){
                return lowestAncester;
            }

            lowestAncester = pathA.get(i);
            i--;
            j--;
        }

        return lowestAncester;
    }

    private List<ParentTreeNode> getPathToRoot(ParentTreeNode node){
        List<ParentTreeNode> res = new ArrayList<>();
        while(node != null){
            res.add(node);
            node = node.parent;
        }

        return res;
    }
}

Binary Tree Path Sum III: http://lintcode.com/en/problem/binary-tree-path-sum-iii/

DFS with the help of parent node

/**
 * 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>> res = new ArrayList<>();
        if(root == null){
            return res;
        }

        dfs(root, target, res);

        return res;
    }

    private void dfs(ParentTreeNode root, int target, List<List<Integer>> res){
        if(root == null){
            return;
        }

        findTarget(root, target, 0, res, new ArrayList<Integer>(), null);

        dfs(root.left, target, res);
        dfs(root.right, target, res);
    }

    private void findTarget(ParentTreeNode root, int target, int sum, List<List<Integer>> res, List<Integer> list
        , ParentTreeNode father){
        sum += root.val;
        list.add(root.val);

        if(sum == target){
            res.add(new ArrayList<>(list));
        }

        if(root.left != null && root.left != father){
            findTarget(root.left, target, sum, res, list, root);
        }

        if(root.right != null && root.right != father){
            findTarget(root.right, target, sum, res, list, root);
        }

        if(root.parent != null && root.parent != father){
            findTarget(root.parent, target, sum, res, list, root);
        }

        list.remove(list.size() - 1);
    }
}