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,用l和r记录从祖先节点搜到当前节点时遇到的最大和最小值,同时更新全局变量ans

 1 #872
 2 #Runtime: 59 ms
 3 #Memory: 19.9 MB
 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 maxAncestorDiff(self, root):
13         """
14         :type root: TreeNode
15         :rtype: int
16         """
17         self.ans = 0
18         def DFS(root, l, r):
19             if not root:
20                 return
21             l = min(root.val, l)
22             r = max(root.val, r)
23             self.ans = max(self.ans, r - l)
24             DFS(root.left, l, r)
25             DFS(root.right, l, r)
26         DFS(root, root.val, root.val)
27         return self.ans

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