LeetCode每日一题-1026.节点与其祖先之间的最大差值

LeetCode 题目

LeetCode-1026.节点与其祖先之间的最大差值

给定二叉树的根节点root, 找出存在于一个节点与其任意一个直接子节点或者间接子节点之间差值的绝对值的最大值.

题目分析

为了差值的绝对值的最大化, 所有子节点的最大值和最小值, 再进行运算求最大差值.

为了找所有子节点的最大值和最小值, 可以使用后序遍历来进行统计.

下面给出的题解内使用两个map来统计子节点中的最大值和最小值.

题解

/**
 * 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 {
private:
    void findMaxDiff(TreeNode *root, unordered_map<TreeNode*, int> &minMap, unordered_map<TreeNode*, int> &maxMap, int &maxDiff) {
        if (!root)
            return;
        findMaxDiff(root -> left, minMap, maxMap, maxDiff); // 递归地找左右孩子的最大差值
        findMaxDiff(root -> right, minMap, maxMap, maxDiff);
        int minVal = root -> val;
        int maxVal = root -> val;
        if (root -> left || root -> right) {    // 左右孩子有一者存在时, 才进行差值的统计
            minVal = INT_MAX;
            maxVal = INT_MIN;
            if (root -> left) {                 // 统计左子树的最大值和最小值
                minVal = min(minMap[root -> left], minVal);
                maxVal = max(maxMap[root -> left], maxVal);
            }
            if (root -> right) {                 // 统计右子树的最大值和最小值
                minVal = min(minMap[root -> right], minVal);
                maxVal = max(maxMap[root -> right], maxVal);
            }
            maxDiff = max({abs(root -> val - minVal), abs(root -> val - maxVal), maxDiff}); // 根据左右子树的最大值和最小值求最大差值
            minMap[root] = min(minVal, root -> val);    // 标记以当前节点为根节点的二叉树中的最大值和最小值
            maxMap[root] = max(maxVal, root -> val);
        } else {    // 没有子节点时, 将最大值和最小值标记为自身
            minMap[root] = minVal;
            maxMap[root] = maxVal;
        }
    }
public:
    int maxAncestorDiff(TreeNode* root) {
        unordered_map<TreeNode*, int> minMap;
        unordered_map<TreeNode*, int> maxMap;
        int maxDiff = 0;
        findMaxDiff(root, minMap, maxMap, maxDiff);
        return maxDiff;
    }
};