Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1026.html

1026. Maximum Difference Between Node and Ancestor (Medium)

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:

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

Related Topics:
Tree, Depth-first Search

Solution 1. Post-order traversal

// OJ: https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/
// Time: O(N)
// Space: O(H)
class Solution {
    int ans = 0;
    pair<int, int> dfs(TreeNode *root) {
        if (!root) return { INT_MAX, INT_MIN };
        auto [lmin, lmax] = dfs(root->left);
        auto [rmin, rmax] = dfs(root->right);
        int mn = min({ root->val, lmin, rmin }), mx = max({ root->val, lmax, rmax });
        ans = max({ ans, abs(root->val - mn), abs(mx - root->val) });
        return { mn, mx };
    }
public:
    int maxAncestorDiff(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

Solution 2.

When traversing down, we update the min and max values we’ve seen from the root to the current node.

At the null pointers of the leave nodes, we calculate the difference between the max and min values we’ve seen since the root.

When traversing up, we return the maximum of the results for the left subtree and the right subtree.

// OJ: https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/
// Time: O(N)
// Space: O(H)
class Solution {
    int dfs(TreeNode *root, int mn, int mx) {
        if (!root) return mx - mn;
        mn = min(mn, root->val);
        mx = max(mx, root->val);
        return max(dfs(root->left, mn, mx), dfs(root->right, mn, mx));
    }
public:
    int maxAncestorDiff(TreeNode* root) {
        return dfs(root, root->val, root->val);
    }
};

Java

  • /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxAncestorDiff(TreeNode root) {
        Map<TreeNode, int[]> nodeValuesMap = new HashMap<TreeNode, int[]>();
        List<TreeNode> nodesList = new ArrayList<TreeNode>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            int value = node.val;
            nodesList.add(node);
            nodeValuesMap.put(node, new int[]{value, value});
            TreeNode left = node.left, right = node.right;
            if (left != null)
                queue.offer(left);
            if (right != null)
                queue.offer(right);
        }
        int maxDifference = 0;
        for (int i = nodesList.size() - 1; i >= 0; i--) {
            TreeNode node = nodesList.get(i);
            int value = node.val;
            int[] values = nodeValuesMap.get(node);
            TreeNode left = node.left, right = node.right;
            if (left != null) {
                int[] leftValues = nodeValuesMap.get(left);
                maxDifference = Math.max(maxDifference, Math.max(Math.abs(value - leftValues[0]), Math.abs(value - leftValues[1])));
                values[0] = Math.min(values[0], leftValues[0]);
                values[1] = Math.max(values[1], leftValues[1]);
            }
            if (right != null) {
                int[] rightValues = nodeValuesMap.get(right);
                maxDifference = Math.max(maxDifference, Math.max(Math.abs(value - rightValues[0]), Math.abs(value - rightValues[1])));
                values[0] = Math.min(values[0], rightValues[0]);
                values[1] = Math.max(values[1], rightValues[1]);
            }
        }
        return maxDifference;
    }
}

  • // OJ: https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/
// Time: O(N)
// Space: O(H)
class Solution {
    int ans = 0;
    pair<int, int> dfs(TreeNode *root) {
        if (!root) return { INT_MAX, INT_MIN };
        auto [lmin, lmax] = dfs(root->left);
        auto [rmin, rmax] = dfs(root->right);
        int mn = min({ root->val, lmin, rmin }), mx = max({ root->val, lmax, rmax });
        ans = max({ ans, abs(root->val - mn), abs(mx - root->val) });
        return { mn, mx };
    }
public:
    int maxAncestorDiff(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

  • # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        def dfs(root, mi, mx):
            if root is None:
                return
            nonlocal ans
            ans = max(ans, abs(mi - root.val), abs(mx - root.val))
            mi = min(mi, root.val)
            mx = max(mx, root.val)
            dfs(root.left, mi, mx)
            dfs(root.right, mi, mx)

        ans = 0
        dfs(root, root.val, root.val)
        return ans

############

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        
        def dfs(node, low, high):
            if not node: return high - low
            
            low = min(low, node.val)
            high = max(high, node.val)
            
            return max(dfs(node.left, low, high), dfs(node.right, low, high))
        
        return dfs(root, root.val, root.val)

All Problems

All Solutions