1026

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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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);
    }
};