问答

当前位置
  • 首页
  • 问答
  • 376.Binary Tree Path Sum: Divide and Conquer分治解法

376.Binary Tree Path Sum: Divide and Conquer分治解法

  • Ta: warrior

我自己尝试写了一下这道题的分治解法,为什么过不了呢?
以下为测试结果:

Input
Show Difference
{1,2,4,2,3}
5
Output
[]
Expected
[[1,2,2],[1,4]]
    List<Integer> path = new ArrayList<>();
    int sum = 0;
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        path.add(root.val);
        sum += root.val;

        if (root.left == null && root.right == null) {
            if (sum == target) {
                result.add(new ArrayList<>(path));  //can also specify <Integer>
            }
            path.remove(path.size() - 1);
            sum -= root.val;
            return result;
        }

        //divide 
        List<List<Integer>> pathsFromLeftSubtree = binaryTreePathSum(root.left, target - root.val);
        List<List<Integer>> pathsFromRightSubtree = binaryTreePathSum(root.right, target - root.val);

        //conquer
        result.addAll(pathsFromLeftSubtree);
        result.addAll(pathsFromRightSubtree);

        path.remove(path.size() - 1);
        sum -= root.val;

        return result;
    }

1 个回复

2019-09-10 Anidlebrain
        List<List<Integer>> pathsFromLeftSubtree = binaryTreePathSum(root.left, target - root.val);
        List<List<Integer>> pathsFromRightSubtree = binaryTreePathSum(root.right, target - root.val);

这两个递归为什么要减去root.val?sum又加上root.val?
要么最后判断target是否等于0,如果要判断sum==target的话那么就不该又加又减

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1