Day105 | 灵神 | 二叉树 出现次数最多的子树元素和

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

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

思路：

核心其实就是要维护遍历过程中的最大值和最小值，然后和本层的结点做减法找到最大值即可

1
2
3
maxVal=max(maxVal,t->val);
minVal=min(minVal,t->val);
res=max(res,max(abs(maxVal-t->val),abs(minVal-t->val)));

可能的疑惑：假如我的最大值或者最小值在左子树，此时我已经遍历到右子树了，那么不会出现A，B两个节点谁都不是谁的祖先吗

这就是搞混了形参和全局变量在递归中的变化导致的

如果作为形参，那么每一层的最大值和最小值都是这一层的，回到根节点的时候也就回溯回去了

如果是全局变量的话才有可能是上面的那种情况

当然这是先序遍历，还可以看一下灵神后序遍历的代码和思路

思路就是递归函数的返回值是最大值和最小值的组成的二元组，从下往上返回最大值和最小值，同时计算对于本层节点来说的最大值和最小值去更新res

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
       int res=0;
       function<void(TreeNode *,int,int)> dfs=[&](TreeNode *t,int maxVal,int minVal)->void{
            if(t==nullptr)
                return;
            maxVal=max(maxVal,t->val);
            minVal=min(minVal,t->val);
            res=max(res,max(abs(maxVal-t->val),abs(minVal-t->val)));
            dfs(t->left,maxVal,minVal);
            dfs(t->right,maxVal,minVal);
       }; 
       dfs(root,root->val,root->val);
       return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//灵神先序遍历
class Solution {
    int ans = 0;

    void dfs(TreeNode *node, int mn, int mx) {
        if (node == nullptr) {
            ans = max(ans, mx - mn);
            return;
        }
        mn = min(mn, node->val);
        mx = max(mx, node->val);
        dfs(node->left, mn, mx);
        dfs(node->right, mn, mx);
    }

public:
    int maxAncestorDiff(TreeNode *root) {
        dfs(root, root->val, root->val);
        return ans;
    }
};

灵神后序遍历代码思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int ans = 0;

    pair<int, int> dfs(TreeNode *node) {
        if (node == nullptr) {
            return {INT_MAX, INT_MIN}; // 保证空节点不影响 mn 和 mx
        }
        auto [l_mn, l_mx] = dfs(node->left);
        auto [r_mn, r_mx] = dfs(node->right);
        int mn = min(node->val, min(l_mn, r_mn));
        int mx = max(node->val, max(l_mx, r_mx));
        ans = max(ans, max(node->val - mn, mx - node->val));
        return {mn, mx};
    }

public:
    int maxAncestorDiff(TreeNode *root) {
        dfs(root);
        return ans;
    }
};