使用 DFS 的 BST 的范围和

Question

问题：给定一棵二叉搜索树的根节点，return所有节点的值在L和R（含）之间的值之和。

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

示例 1：

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

输出：32

力扣题：https://leetcode.com/problems/range-sum-of-bst/

我的方法： 我正在尝试做一个 dfs 并访问每个节点，如果该节点的值符合约束，那么我想 return 它在我的递归函数中。然后我将所有值和 return 加到我的主要函数中。

我仍在努力理解递归，我在这段代码中做错了什么（为什么它只有 return 10 而不是 32？）。

我正在尝试 return 每个递归函数的一个值并将其添加到最后 - 这样做有意义吗？

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

您在末尾添加这些值并使用 return 值的方法是正确的。（在使用指针算法或通过引用变量传递的语言中，您可以传递对整数的引用并增加重新计算的值，而无需 return 值。）但是在符合“return root.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 范围之间时，算法应该更深入地重复，而不是你的 returns 当前节点自己的值而不看更深。
算法不应该总是需要访问每个节点，而是利用BST 属性：它应该只在左边搜索当前值不排除在该子树中查找任何 in-range 值时的子树。

例如，如果当前节点的值为 3，并且 L-R 范围是 (5,9)，那么在左子树中进一步查找是没有意义的，因为 all 值保证小于 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;
    }
}

使用 DFS 的 BST 的范围和

Range Sum of BST using DFS

java

tree

recursion

binary-tree

depth-first-search