6731619490960_.pic.jpg

题目描述

leetcode 第938题：二叉搜索树的范围和
给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
输入：root = [10,5,15,3,7,null,18], low = 7, high = 15

bst1.jpeg

输出：32

解题方法

DFS
参考题解

• 解题思路

对于二叉搜索树，左子树上所有节点的值<根节点的值<右子树上所有节点的值
使用DFS的思路计算在[low,high]区间内所有结点的值的和
每次DFS，考虑以下4种情况：
若不存在当前节点root时，返回0
若当前节点的值小于low时，无需考虑左子树，返回右子树DFS计算的和
若当前节点的值大于high时，无需考虑右子树，返回左子树DFS计算的和
若当前节点的值在区间内时，返回当前节点的值+右子树DFS计算的和+左子树DFS计算的和

• 复杂度

时间复杂度：O(n)，n 为二叉搜索树的节点数
空间复杂度：O(n)

• 代码实现

python3

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        if root==None:
            return 0
        if root.val<low:
            return self.rangeSumBST(root.right,low,high)
        if root.val>high:
            return self.rangeSumBST(root.left,low,high)
        return root.val+self.rangeSumBST(root.left,low,high)+self.rangeSumBST(root.right,low,high)

php

class Solution {
    function rangeSumBST($root, $low, $high) {
        if($root==null){
            return 0;
        }
        if($root->val<$low){
            return $this->rangeSumBST($root->right,$low,$high);
        }
        if($root->val>$high){
            return $this->rangeSumBST($root->left,$low,$high);
        }
        return $root->val+$this->rangeSumBST($root->left,$low,$high)+$this->rangeSumBST($root->right,$low,$high);
    }
}