Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
求二叉树所有节点的节点值最小的差值
用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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理