原题链接在这里:
题目:
- Given the root of a binary tree, find the maximum value V for which there exists different nodes A and B where V = |A.val - B.val| and A is an ancestor of B.
- (A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)
- Example 1:
- Input: [8,3,10,1,6,null,14,null,null,4,7,13]
- Output: 7
- Explanation:
- We have various ancestor-node differences, some of which are given below :
- |8 - 3| = 5
- |3 - 7| = 4
- |8 - 1| = 7
- |10 - 13| = 3
- Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.
- Note:
- The number of nodes in the tree is between 2 and
- 5000
- .
- Each node will have value between 0 and
- 100000
- .
题解:
Perform DFS top down. On each level, Calculate maxmimum difference and update minimum and maximum value.
- Time Complexity: O(n).
- Space: O(h).
- AC Java:
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- int res = 0;
- public int maxAncestorDiff(TreeNode root) {
- if(root == null){
- return res;
- }
- dfs(root, root.val, root.val);
- return res;
- }
- private void dfs(TreeNode root, int min, int max){
- if(root == null){
- return;
- }
- res = Math.max(res, Math.max(Math.abs(root.val - min), Math.abs(max-root.val)));
- min = Math.min(min, root.val);
- max = Math.max(max, root.val);
- dfs(root.left, min, max);
- dfs(root.right, min, max);
- }
- }
来源: http://www.bubuko.com/infodetail-3116095.html