给定一棵二叉树和一个总和，找到所有根到叶的路径，其中每条路径的总和等于给定的总和

Question

为什么最后用的是"path.remove(path.size()-1)"

此代码用于查找总和等于给定总和的所有根到叶路径。

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    ArrayList<Integer> path = new ArrayList<Integer>();
    pathSumRe(root, sum, res, path);
    return res;
}
public void pathSumRe(TreeNode root, int sum, List<List<Integer>> res,
        ArrayList<Integer> path) {

    if (root == null)
        return;

    path.add(root.val);

    if (root.left == null && root.right == null && root.val == sum) {

        ArrayList<Integer> tmp = new ArrayList<Integer>(path);
        res.add(tmp);
    }

    pathSumRe(root.left, sum - root.val, res, path);
    pathSumRe(root.right, sum - root.val, res, path);
    path.remove(path.size() - 1);
}

从代码中删除 "path.remove(path.size() - 1);" 将得到以下输出。

输入：[0,1,1], 1

输出：[[0,1],[0,1,1]] ==> 这是错误的输出

预期输出：[[0,1],[0,1]]

Answer 1

path.remove(path.size() - 1) 正在从 path 列表中删除最后添加的节点，因为您正在为所有递归迭代重复使用相同的列表，并且正在添加带有 path.add(root.val); 的当前节点每个方法执行。

如果不重复使用同一个列表（并为每次执行创建一个新列表），以下内容是等效的：

public void pathSumRe(TreeNode root, int sum, List<List<Integer>> res,
        ArrayList<Integer> path) {
    if (root == null) {
        return;
    }
    path.add(root.val);
    if (root.left == null && root.right == null && root.val == sum) {
        res.add(new ArrayList<Integer>(path));
    }
    pathSumRe(root.left, sum - root.val, res, new ArrayList<Integer>(path));
    pathSumRe(root.right, sum - root.val, res, new ArrayList<Integer>(path));
}

这更容易理解，但会创建更多新的 ArrayLists（取决于树结构）。无论您进行何种编辑，对于这样的 TreeNode，两个版本都可以正常工作：

class TreeNode {
    public final int val;
    public final TreeNode left;
    public final TreeNode right;

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Answer 2

这是干净的 Java 实现：

public static List<List<Integer>> rootToLeafPathsForSum(BinaryTreeNode<Integer> node, int requiredSum) {
    List <List<Integer>> paths = new ArrayList<List<Integer>>();
    doFindRootToLeafPathsForSum(node, 0, requiredSum, new ArrayList<Integer>(), paths);
    return paths;
}

private static void doFindRootToLeafPathsForSum(BinaryTreeNode<Integer> node, int sum, int requiredSum,
        List<Integer> path, List<List<Integer>> paths) {
    if(node == null) {
        return ;
    } 
    path.add(node.getData());
    sum +=node.getData();
    if (node.isLeafNode()) {
        if (sum == requiredSum) {
            paths.add(new ArrayList<Integer>(path));
        }           
    } else {
        doFindRootToLeafPathsForSum(node.getLeft(), sum,  requiredSum, path, paths);
        doFindRootToLeafPathsForSum(node.getRight(), sum, requiredSum, path, paths);

    }
    path.remove(node.getData());
}

这里是测试用例

@Test
public void allRoot2LeafPathsForGivenSum() {
    BinaryTreeNode<Integer> bt = buildTree();
    List <List<Integer>> paths = BinaryTreeUtil.rootToLeafPathsForSum(bt, 14);

    assertThat(paths.size(), is(2));

    assertThat(paths.get(0).toArray(new Integer[0]), equalTo(new Integer[]{1,2,5,6}));
    assertThat(paths.get(1).toArray(new Integer[0]), equalTo(new Integer[]{1,3,7,3}));

    for (List<Integer> list : paths) {          
        for (Integer integer : list) {
            System.out.print(String.format(" %d", integer));
        }
        System.out.println();
    }
}

private BinaryTreeNode<Integer> buildTree() {
    BinaryTreeNode<Integer> n4 = new BinaryTreeNode<Integer>(4);
    BinaryTreeNode<Integer> n6 = new BinaryTreeNode<Integer>(6);
    BinaryTreeNode<Integer> n5 = new BinaryTreeNode<Integer>(5, null, n6);
    BinaryTreeNode<Integer> n2= new BinaryTreeNode<Integer>(2, n4, n5);
    BinaryTreeNode<Integer> n31 = new BinaryTreeNode<Integer>(3);
    BinaryTreeNode<Integer> n7 = new BinaryTreeNode<Integer>(7, null, n31);
    BinaryTreeNode<Integer> n3 = new BinaryTreeNode<Integer>(3, n7, null);
    BinaryTreeNode<Integer> root = new BinaryTreeNode<Integer>(1, n2, n3);

    return root;
}

Answer 3

您需要的是检查到现在遍历的路径的方法，如果是，则求和到叶子求和，如果是，则将该列表添加到结果，否则，您需要回溯，这是本例中最重要的一步！我希望代码能让它更清楚 -

void util(TreeNode root, int sum, ArrayList<Integer>log, ArrayList<ArrayList<Integer>> result)
{
    if(root == null)    
        return;
    log.add(root.val);
    if(root.left == null && root.right == null && sum - root.val == 0)
        result.add(new ArrayList<Integer>(log));
    util(root.left, sum-root.val, log, result);
    util(root.right, sum-root.val, log, result);
    log.remove(log.size()-1);
}

给定一棵二叉树和一个总和，找到所有根到叶的路径，其中每条路径的总和等于给定的总和

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum

java

binary-tree