题目如下:
解题思路:题目要求最大的差值的绝对值。对于任意一个节点来说,其可以得到的最大差值的绝对值只有在这四种情况中:与左子树的最大值,与左子树的最小值,与右子树的最大值,与右子树的最小值。所以只要遍历树,求出每个节点的最大差值,即可得到整棵树的最大差值。当然,为了提高效率,可以缓存每个节点的左子树的最大值、左子树的最小值、右子树的最大值、右子树的最小值。
代码如下:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution(object):
dic = {} #(max,min)
res = 0
def recursive(self,node,num):
self.dic[num] = (-float('inf'),float('inf'))
if node.left != None:
if num*2 not in self.dic:
self.recursive(node.left, num * 2)
self.res = max(self.res,abs(node.val - self.dic[num*2][0]),abs(node.val - self.dic[num*2][1]))
self.dic[num] = (max(node.val,self.dic[num][0],self.dic[num*2][0]),min(node.val,self.dic[num][1],self.dic[num*2][1])) if node.right != None:
inx = num*2 + 1
if inx not in self.dic:
self.recursive(node.right, num * 2+1)
self.res = max(self.res,abs(node.val - self.dic[inx][0]),abs(node.val - self.dic[inx][1]))
self.dic[num] = (max(node.val,self.dic[num][0],self.dic[inx][0]),min(node.val,self.dic[num][1],self.dic[inx][1])) if node.left == None and node.right == None:
self.dic[num] = (node.val,node.val) def maxAncestorDiff(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.dic = {}
self.res = 0
self.recursive(root,1)
#print self.dic
return self.res