给一棵二叉树,问书中某个子节点和它某个祖先节点的数值差最大多少
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