具有给定总和的二叉树中的路径数

Question

我正在解决问题https://leetcode.com/problems/path-sum-iii/ 我还会在这里简单提一下:找到二叉树中sum = sum的路径数.该路径不一定必须在根(叶)处开始(结束).只要路径向下,就应该将其视为有效路径.

这是我的解决方案:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class Solution {
    public int pathSum(TreeNode root, int sum) {
        int path = 0;
        if(root.val == sum)
            return 1;
        else if(root.left == null && root.right == null)
            return 0;
        if(root.left != null){
            path += pathSum(root.left, sum - root.val);
            path += pathSum(root.left, sum);
        }
        if(root.right != null){
            path += pathSum(root.right, sum - root.val);
            path += pathSum(root.right, sum);
        }
        return path;
    }
}

根据他们的系统的答案是3,但我得到以下输入的答案为4:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

我花了好几个小时试图解释为什么我的代码不起作用,但我无法弄清楚问题.

抱歉一个天真的问题:(但这是杀了我!

Answer 1

我不确定你的解决方案有什么问题,但我不认为这是正确的.首先,如果你的root是8,你会立即返回并只计算根作为解决方案.我就是这样做的:

import java.util.ArrayList;

public class Solution {
    public static int pathSum(TreeNode root, int sum) {
      return pathSum(root, sum, 0, new ArrayList<Integer>());
    }

    public static int pathSum(TreeNode root, int sum, int count, ArrayList<Integer> arr) {
        arr.add(root.val);
        int acc = 0;
        for (int i=arr.size()-1; i>=0; i--) {
          acc += arr.get(i);
          if (acc == sum)
            count++;
        }
        if(root.left != null)
            count = pathSum(root.left, sum, count, arr);
        if(root.right != null)
            count = pathSum(root.right, sum, count, arr);
        arr.remove(arr.size()-1);
        return count;
    }

  static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int v) {
      this.val = v;
    }
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(10);
    root.left = new TreeNode(5);
    root.right = new TreeNode(-3);
    root.left.left = new TreeNode(3);
    root.left.right = new TreeNode(2);
    root.right.right = new TreeNode(11);
    root.left.left.left = new TreeNode(3);
    root.left.left.right = new TreeNode(-2);
    root.left.right.right = new TreeNode(1);
    System.out.println(pathSum(root, 8));
  }
}

我们的想法是在递归遍历树时使用路径中的值填充aarray,确保在返回时删除元素.当您访问节点时,您必须考虑从该节点到根路径上的任何节点的所有总和.其中任何一个都可以累加到您的参考值.当你遍历n个节点时,这个实现是O(nlogn),并且每个遍历一个len的数组到log(n).