【Leetcode_总结】 938. 二叉搜索树的范围和 - python

Q:

给定二叉搜索树的根结点 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

---

链接：https://leetcode-cn.com/problems/range-sum-of-bst/description/

思路：前序遍历二叉树，如果值在L R之间，就相加

代码：

# 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
        """
        result, stack = 0, [root]
        while stack:
            node = stack.pop()
            if node:
                if L <= node.val <= R:
                    result += node.val
                if node.val < R:
                    stack.append(node.right)
                if L < node.val:
                    stack.append(node.left)          
        return result

---

另一种方法是中序遍历，然后返回L,R之间的和

代码：

# 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
        """
        if root == None:
            return []
        else:
            res = []
            self.middle_digui(root, res)
        return (sum(res[res.index(L):res.index(R)+1]))

    def middle_digui(self,root,res):
        if root == None:
            return
        self.middle_digui(root.left,res)
        res.append(root.val)
        self.middle_digui(root.right,res)