1026. Maximum Difference Between Node and Ancestor.md

1026. Maximum Difference Between Node and Ancestor

---

leetcode Daily Challenge on November 9th, 2020.

---

Difficulty : Medium

Related Topics : Tree、DFS

---

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.

Example 2:

Input: root = [1,null,2,null,0,3]
Output: 3

Note:

• The number of nodes in the tree is between 2 and 5000.
• Each node will have value between 0 and 100000.

---

Solution

• mine
  • Java
    • DFS Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.6 MB, less than 5.55% of Java online submissions

      public int res;
      public int maxAncestorDiff(TreeNode root) {
          dfs(root, root.val, root.val);
          return res;
      }
      
      public void dfs(TreeNode node,int max,int min){
          if(node == null){
              res = Math.max(res, Math.abs(max-min));
              return;
          }
          max = Math.max(node.val, max);
          min = Math.min(node.val, min);
          dfs(node.left, max, min);
          dfs(node.right, max, min);
      }
      

---

• the most votes

• DFS Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.8 MB, less than 5.55% of Java online submissions

  public int maxAncestorDiff(TreeNode root) {
      return dfs(root, root.val, root.val);
  }
  
  public int dfs(TreeNode root, int mn, int mx) {
      if (root == null) return mx - mn;
      mx = Math.max(mx, root.val);
      mn = Math.min(mn, root.val);
      return Math.max(dfs(root.left, mn, mx), dfs(root.right, mn, mx));
  }
  

---