Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
求二叉搜索树中元素值之差最小是多少,DFS中序遍历的同时记录当前节点和上一次访问的节点值之差即可


 1 #530
 2 #Runtime: 44 ms (Beats 43.16%)
 3 #Memory: 17.3 MB (Beats 71.85%)
 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 class Solution(object):
12     def getMinimumDifference(self, root):
13         """
14         :type root: TreeNode
15         :rtype: int
16         """
17         self.ans = 100000
18         self.pre_val = None
19 
20         def DFS(node):
21             if not node:
22                 return        
23             DFS(node.left)
24             if self.pre_val is not None:
25                 self.ans = min(self.ans, node.val - self.pre_val)
26             self.pre_val = node.val
27             DFS(node.right)
28 
29         DFS(root)
30         return self.ans

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