leetcode938 -- Range Sum of BST

leetcode938 -- Range Sum of BST

题目


Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

 

Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32
Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

解答

我想的是先用中序遍历一遍,得到一个排好序的数组,然后再加和


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

class Solution:
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        if not root:
            return 
        
        res = []
        self.inorder(root, res)
        summ = 0
        for x in res:
            if x>=L and x<=R:
                summ += x
            
            if x>R:
                break
        
        return summ 
    
    
    def inorder(self, root, res):
        if not root:
            return 
        
        self.inorder(root.left, res)
        res.append(root.val)
        self.inorder(root.right, res)

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦