1026.Maximum Difference Between Node and Ancestor
===

###### tags: `Medium`,`Tree`,`Binary Tree`,`DFS`

[1026. Maximum Difference Between Node and Ancestor](https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/)

### 題目描述

Given the `root` of a binary tree, find the maximum value `v` for which there exist **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: root = [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

**Constraints**:

* The number of nodes in the tree is in the range `[2, 5000]`.
* 0 <= `Node.val` <= 10^5^

### 解答
#### Python

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        self.currMaxDiff = 0
        def getMaxDiff(node, currMax, currMin):
            if not node: 
                return

            currMax = max(currMax, node.val)
            currMin = min(currMin, node.val)
            self.currMaxDiff = max(self.currMaxDiff, abs(node.val - currMax), abs(node.val - currMin))
            getMaxDiff(node.left, currMax, currMin)
            getMaxDiff(node.right, currMax, currMin)

        getMaxDiff(root, root.val, root.val)
        return self.currMaxDiff

> [name=Kobe][time= Dec 9, 2022]

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        def current_subtree_min(root):
            Q = [root.val]
            child_maxdiff = []
            if root.left != None:
                left_diff, left_limit = current_subtree_min(root.left)
                Q += left_limit
                child_maxdiff.append(left_diff)
            if root.right != None:
                right_diff, right_limit = current_subtree_min(root.right)                            
                Q += right_limit
                child_maxdiff.append(right_diff)
            
            #print(root.val, max( [ abs(root.val - x) for x in Q] ), [min(Q), max(Q)])
            #print( [abs(root.val - x) for x in Q])
            return max( child_maxdiff+[ abs(root.val - x) for x in Q] ), [min(Q), max(Q)]
        
        ans , _ = current_subtree_min(root)
        return ans

> [name=玉山][time= Dec 10, 2022]

#### C++

class Solution {
public:
    int maxAncestorDiff(TreeNode* root, int alpha = INT_MAX, int beta = INT_MIN) {
        if (!root) return 0;
        alpha = min(alpha, root->val);
        beta = max(beta, root->val);
        return root->left == root->right ? beta - alpha : max(maxAncestorDiff(root->left, alpha, beta), maxAncestorDiff(root->right, alpha, beta));
    }
};

> [name=Yen-Chi Chen][time=Fri, Dec 9, 2022]

#### C#

public class Solution {
    public int MaxAncestorDiff(TreeNode root) {
        return MaxAncestorDiff(root, root.val, root.val);
    }

    private int MaxAncestorDiff(TreeNode node, int min, int max){
        if (node == null) return 0;
        
        min = Math.Min(node.val, min);
        max = Math.Max(node.val, max);
        
        int diff = max - min;
        diff = Math.Max(diff, MaxAncestorDiff(node.left, min, max));
        diff = Math.Max(diff, MaxAncestorDiff(node.right, min, max));

        return diff;
    }
}

> [name=Jim][time=Fri, Dec 9, 2022]

#### Javascript

function maxAncestorDiff(root) {
  if (root === null) return 0;
  return dfs(root, root.val, root.val);
}

function dfs(node, min, max) {
  if (node === null) return max - min;
  min = Math.min(min, node.val);
  max = Math.max(max, node.val);
  return Math.max(dfs(node.left, min, max), dfs(node.right, min, max));
}

> [name=Marsgoat][time=Tue, Feb 21, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)