Posted on 2023-02-17 20:56
Uriel 閱讀(54)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
數據結構 、
閑來無事重切Leet Code
求二叉樹所有節點的節點值最小的差值
用SortedList存遍歷二叉樹記錄的所有節點值，然后O(n)掃一遍計算相鄰值的最小差值
1 #783
2 #Runtime: 25 ms (Beats 23.66%)
3 #Memory: 13.9 MB (Beats 10.75%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 from sortedcontainers import SortedList
12
13 class Solution(object):
14 def minDiffInBST(self, root):
15 """
16 :type root: TreeNode
17 :rtype: int
18 """
19 val = SortedList()
20
21 def DFS(node):
22 if not node:
23 return
24 val.add(node.val)
25 DFS(node.left)
26 DFS(node.right)
27
28
29 DFS(root)
30 pre = val[0]
31 ans = 100001
32 for i in range(1, len(val)):
33 print(val[i])
34 ans = min(ans, abs(val[i] - pre))
35 pre = val[i]
36 return ans