Atrist

# 二叉搜索树的范围和

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

# 示例1：

输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32

# 示例 2：

输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23

# 分析

它是一个二叉搜索树, 二叉搜索树的中序遍历会是一个递增序列, 所以可以进行判断，然后进行求和

# 代码

var rangeSumBST = function(root, low, high) {
    let res = 0
    const dfs_b = (node)=>{
        node.left && dfs_b(node.left)
        if(node.val >= low && node.val <= high) res += node.val
        node.right && dfs_b(node.right)
    }
    dfs_b(root)
    return res
};

# 优化

进行对递归条件的再次优化, 即官方的深度优先遍历的实现

记当前节点为root, 分以下四种情况讨论:

  1. root 节点为空，返回 0
  2. root 节点值大于 high, 则说明右子树上的无须在遍历，便返回左子树
  3. root 节点值 小于low, , 则说明左子树上的无须在遍历，便返回右子树
  4. oot 节点的值在 [low,high] 范围内， 返回三者之和
var rangeSumBST = function(root, low, high) {
    if (!root) {
        return 0;
    }
    if (root.val > high) {
        return rangeSumBST(root.left, low, high);
    }
    if (root.val < low) {
        return rangeSumBST(root.right, low, high);
    }
    return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
}

# 参考资料