Posted on 2023-02-17 20:56
Uriel 阅读(26)
评论(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