34 二叉树中和为某一值的路径

牛客

描述

输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
    ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    if(root==null) return ret;
    ArrayList<Integer> path = new ArrayList<>();
    findPath(root, expectNumber, ret, path, 0);
    return ret;
}

private void findPath(TreeNode root, int expectedSum, ArrayList<ArrayList<Integer>> ret, 
                        ArrayList<Integer> path, int currentSum){
    currentSum += root.val;
    path.add(root.val);
    
    if(root.left==null && root.right==null && currentSum==expectedSum){
        ArrayList<Integer> newPath = (ArrayList<Integer>) path.clone();
        ret.add(newPath);
    }
    
    if(root.left!=null){
        findPath(root.left, expectedSum, ret, path, currentSum);
    }
    if(root.right!=null){
        findPath(root.right, expectedSum, ret, path, currentSum);
    }
    path.remove(path.size()-1);
}