Leetcode 938.二叉搜索树的范围和

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

方法

方法1：递归中序遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def __init__(self):
        self.sum=0

    def rangeSumBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: int
        """
        if root is None:
            return 0

        self.rangeSumBST(root.left,L,R)
        if L<=root.val<=R:
            self.sum+=root.val
        self.rangeSumBST(root.right,L,R)     
        return self.sum

方法2：递归深度优先遍历（先序遍历）

采用深度搜先方法遍历二叉树，如果$node.val$在[L,R]范围之外（比如$node.val

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution(object): def rangeSumBST(self, root, L, R): def dfs(node): if node: if L <= node.val <= R: self.ans += node.val if L < node.val: dfs(node.left) if node.val < R: dfs(node.right) self.ans = 0 dfs(root) return self.ans

方法3：非递归的深度优先遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def rangeSumBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: int
        """
        ans=0
        stack=[root]
        while stack:
            t=stack.pop()
            if t:
                if L<=t.val<=R:
                    ans+=t.val
                if L<t.val:
                    stack.append(t.left)
                if t.val<R:
                    stack.append(t.right)
        return ans