938. 二叉搜索树的范围和

给定二叉搜索树的根结点 root,返回 L 和 R(含)之间的所有结点的值的和。

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

 

示例 1:
输入:root = [10,5,15,3,7,null,18], L = 7, R = 15
输出:32

示例 2:
输入:root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
输出:23

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/range-sum-of-bst
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} L
 * @param {number} R
 * @return {number}
 */
var rangeSumBST = function(root, L, R) {
    if (root == null) {
        return 0
    }
    if (root.val < L) {
        return rangeSumBST(root.right, L, R)
    } else if (R < +root.val) {
        return rangeSumBST(root.left, L, R)
    } else {
        return root.val + rangeSumBST(root.right, L, R) + rangeSumBST(root.left, L, R)
    }
};

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注