使用DFS的BST范围和

Question

问题：给定二叉查找树的根节点，返回值在L和R（包括）之间的所有节点的值之和。

二叉搜索树保证具有唯一的值。

例1：

输入：root=[10,5,15,3,7，null，18]，L=7，R=15

输出： 32

Leetcode问题：https://leetcode.com/problems/range-sum-of-bst/

我的方法是：我尝试执行dfs并访问每个节点，如果该节点上的值符合约束条件，那么我希望在递归函数中返回它。然后，我将所有值相加，并将其返回到我的主函数。

我仍然试图理解递归，我在这段代码中做错了什么（为什么它只返回10而不是32？）。

我试图从每个递归函数返回一个值，并在最后添加它——这样做有意义吗？

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        if(root == null) {
            return 0;
        }

        rangeBST(root, L, R);
        
        return rangeBST(root, L, R);
    }
    
    public static int rangeBST(TreeNode root, int L, int R) {
        if(root == null) {
            return 0;
        }
        
        if(root.val >= L && root.val <= R) {
            return root.val;
        }

        int x = rangeBST(root.left, L, R);
        int y = rangeBST(root.right, L, R);
        
        return x + y;
    }
}

Answer 1

您在末尾添加这些值并使用返回值的方法是正确的。（在使用指针算术或通过引用变量传递的语言中，可以将引用传递给整数并增加接收值，而无需返回值。）但在使用“returnroot.val”时，您遇到了一个问题。

public int rangeSumBST(TreeNode root, int l, int r) {
        if(root == null)
            return 0;

        // This is a problem because you are stopping with your recursive search
        // if one value was found. This is the reason because it is returning 10 in your example
        // if(root.val >= L && root.val <= R) return root.val;

        int result = 0;
        // So your looking at your node, if the value is in the range you want.
        if (root.val >= l && root.val <= r)
            result += root.val;

        // Add the ranged summ of your left node
        result += rangeSumBST(root.left, l, r);
        // Add the ranged summ of your right node
        result += rangeSumBST(root.right, l, r);

        // And your done
        return result;
    }

Answer 2

两个问题：

>

当值在L-R范围之间时，该算法应更深入地重现，但返回当前节点自己的值时，不会再深入查看。

算法不应该总是需要访问每个节点，而是利用BST属性：它应该只在当前值不排除时在左侧子树中搜索，以便在该子树中找到任何范围内的值。

例如，如果当前节点的值为3，且L-R范围为（5,9），则进一步查看左子树是没有意义的，因为在左子树中，所有值都保证小于3，无论该子树有多大。

右子树也有类似的观察结果。

class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) return 0;
        int val = 0;
        if (root.val >= L && root.val <= R) val += root.val;
        if (root.val < R) val += rangeSumBST(root.right, L, R);
        if (root.val > L) val += rangeSumBST(root.left, L, R);
        return val;
    }
}