938. Range Sum of BST

https://leetcode.com/problems/range-sum-of-bst/description/

solution

类似树的直径写法

class Solution:
    def __init__(self):
        self.res = 0

    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        self.dfs(root, low, high)
        return self.res

    def dfs(self, root, low, high):
        if not root:
            return 0

        if root.val < low:
            self.dfs(root.right, low, high)
        elif root.val > high:
            self.dfs(root.left, low, high)
        else:
            self.res += root.val
            self.dfs(root.left, low, high)
            self.dfs(root.right, low, high)

• 以下两种方法有助于加深对递归和BST理解

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if not root:
            return 0

        if root.val < low:
            # 返回了其子节点的结果，也意味着本节点没有被处理
            return self.rangeSumBST(root.right, low, high)

        elif 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)

时间复杂度：O(n) 空间复杂度：O(h)

class Solution:
    def __init__(self):
        self.res = 0

    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if not root:
            return 0

        if root.val < low:
            self.rangeSumBST(root.right, low, high)

        if root.val > high:
            self.rangeSumBST(root.left, low, high)

        # 理解为: 迭代过程中遇到范围内的加到sum中, 但要考虑二叉树遍历过程中sum的传递与返回
        if low <= root.val <= high:
            self.res += root.val
            self.rangeSumBST(root.left, low, high)
            self.rangeSumBST(root.right, low, high)
        return self.res