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

Question

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

这是我的解决方案:

/**
 * 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

我不确定您的解决方案有什么问题，但我认为它不正确。一方面，如果您的根是 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));
  }
}

这个想法是在递归遍历树时用沿路径的值填充数组，确保在返回时删除元素。当您访问一个节点时，您必须考虑从该节点到根路径上的任何节点的所有总和。它们中的任何一个加起来都可以成为您的引用值。此实现是 O(nlogn)，因为您遍历 n 个节点，并且对于每个节点，您遍历一个 len 数组直到 log(n)。