Re: [閒聊] 每日LeetCode

看板Marginalman作者pandix (麵包屌)時間3年前 (2022/12/07 13:59)推噓2(2推 0噓 2→)

留言4則, 4人參與討論串129/719 (看更多)

938. Range Sum of BST 給你一棵 binary search tree 還有目標 range = [low, high] 要你回傳這棵樹中 value 介於 [low, high] 間的所有 node 的總和 Example 1: https://assets.leetcode.com/uploads/2020/11/05/bst1.jpg

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15 Output: 32 Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32. Example 2: https://assets.leetcode.com/uploads/2020/11/05/bst2.jpg

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10 Output: 23 Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23. 思路: 1.其實可以當成 binary tree 直接找所有 node 就好左右子樹都遞迴下去找把那些 low <= value <= high 的 node 加起來就好時間複雜度O(node數) 2.要用到 BST 的性質的話就是把 value 和 low, high 拿去比較 value > high 的話: value 右子樹全部都比 high 大，所以不用遞迴找右子樹 value < low 的話: value 左子樹全部都比 low 小，所以不用遞迴找左子樹時間複雜度不變就是了 Python code: # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int: if not root: return 0 res = 0 if root.val <= high: res += self.rangeSumBST(root.right, low, high) if root.val >= low: res += self.rangeSumBST(root.left, low, high) if low <= root.val <= high: res += root.val return res -- 蛤? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.204.64 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1670392755.A.0FC.html

推

wwndbk

12/07 14:00, 3年前 , 1^F

12/07 14:00, 1^F

→

Rushia

12/07 14:03, 3年前 , 2^F

12/07 14:03, 2^F

→

DDFox

12/07 14:04, 3年前 , 3^F

12/07 14:04, 3^F