|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +Given the root of a binary tree, find the maximum value V for which there exists |
| 4 | +different nodes A and B where V = |A.val - B.val| and A is an ancestor of B. |
| 5 | +
|
| 6 | +(A node A is an ancestor of B if either: any child of A is equal to B, or any |
| 7 | +child of A is an ancestor of B.) |
| 8 | +
|
| 9 | +Example 1: |
| 10 | +Input: [8,3,10,1,6,null,14,null,null,4,7,13] |
| 11 | +Output: 7 |
| 12 | +Explanation: |
| 13 | +We have various ancestor-node differences, some of which are given below : |
| 14 | +|8 - 3| = 5 |
| 15 | +|3 - 7| = 4 |
| 16 | +|8 - 1| = 7 |
| 17 | +|10 - 13| = 3 |
| 18 | +Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = |
| 19 | +7. |
| 20 | +
|
| 21 | +Note: |
| 22 | +The number of nodes in the tree is between 2 and 5000. |
| 23 | +Each node will have value between 0 and 100000. |
| 24 | +""" |
| 25 | + |
| 26 | + |
| 27 | +# Definition for a binary tree node. |
| 28 | +classTreeNode: |
| 29 | +def__init__(self,x): |
| 30 | +self.val=x |
| 31 | +self.left=None |
| 32 | +self.right=None |
| 33 | + |
| 34 | + |
| 35 | +classSolution: |
| 36 | +def__init__(self): |
| 37 | +self.ret=0 |
| 38 | + |
| 39 | +defmaxAncestorDiff(self,root:TreeNode)->int: |
| 40 | +""" |
| 41 | + dfs return min and max |
| 42 | + """ |
| 43 | +self.dfs(root) |
| 44 | +returnself.ret |
| 45 | + |
| 46 | +defdfs(self,node): |
| 47 | +ifnotnode: |
| 48 | +returnfloat("inf"),-float("inf") |
| 49 | + |
| 50 | +lmin,lmax=self.dfs(node.left) |
| 51 | +rmin,rmax=self.dfs(node.right) |
| 52 | +mini=min(lmin,rmin) |
| 53 | +maxa=max(lmax,rmax) |
| 54 | +ifmini!=float("inf"): |
| 55 | +self.ret=max(self.ret,abs(mini-node.val)) |
| 56 | +ifmaxa!=-float("inf"): |
| 57 | +self.ret=max(self.ret,abs(maxa-node.val)) |
| 58 | + |
| 59 | +returnmin(mini,node.val),max(maxa,node.val) |