1026.Maximum Difference Between Node and Ancestor

tags: Medium,Tree,Binary Tree,DFS

1026. 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⁵

解答

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

Kobe 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

玉山 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));
    }
};

Yen-Chi ChenFri, 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;
    }
}

JimFri, 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));
}

MarsgoatTue, Feb 21, 2023

Reference

回到題目列表