20240110-节点和祖先之间的最大差异

题目要求

给定一棵二叉树的根，求存在不同节点 a 和 b 的最大值 v，其中 v = |a.val - b.val|，且 a 是 b 的祖先。

节点 a 是 b 的祖先，如果： a 的任何子节点等于 b 或 a 的任何子节点是 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.

思路

一道二叉树的操作题，要求返回所有可能的祖先和子孙的差的最大值。对于每个子树，找到其后代的最小值和最大值。因为需要左右子树的返回值都拿到才能处理中间节点，所以采用后序遍历。

代码

/**
 * 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 result = INT_MIN;
    pair<int, int> traversal(TreeNode* root) {
        if (!root) {
            return {INT_MAX, INT_MIN};
        }
        // res.first = min, res.second = max;
        pair<int, int> left_res = root->left ? traversal(root->left) : make_pair(INT_MAX, INT_MIN);
        pair<int, int> right_res = root->right ? traversal(root->right) : make_pair(INT_MAX, INT_MIN);
        int local_min = min({root->val, left_res.first, right_res.first});
        int local_max = max({root->val, left_res.second, right_res.second});
        if (root->left || root->right) {
            int local_res = max(abs(root->val - local_max), abs(root->val - local_min));
            result = max(result, local_res);
        }
        return {local_min, local_max};
    }

    int maxAncestorDiff(TreeNode* root) {
        traversal(root);
        return result;
    }
};