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.

Top-down

c++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    int res = 0;
    pair<int, int> dfs(TreeNode* node) {
        int mi = node->val;
        int ma = node->val;

        if(node->left) {
            auto [lmi, lma] = dfs(node->left);
            mi = min(mi, lmi);
            ma = max(ma, lma);
            res = max({res, abs(node->val - mi), abs(node->val - ma)});
        }

        if(node->right) {
            auto [rmi, rma] = dfs(node->right);
            mi = min(mi, rmi);
            ma = max(ma, rma);
            res = max({res, abs(node->val - mi), abs(node->val - ma)});
        }
        return {mi, ma};
    }
public:
    int maxAncestorDiff(TreeNode* root) {
        dfs(root);
        return res;
    }
};

Bottom-up

c++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxAncestorDiff(TreeNode* root, int mi = 100000, int ma = 0) {
        if(!root) return ma -  mi;
        mi = min(mi, root->val);
        ma = max(ma, root->val);
        return max(maxAncestorDiff(root->left, mi, ma), maxAncestorDiff(root->right, mi, ma));
    }
};