多说与网站账号绑定,学校网站管理系统,微信公众号h5商城网站开发,wordpress主题Modown破解1026. 节点与其祖先之间的最大差值 - 力扣#xff08;LeetCode#xff09; 给定二叉树的根节点 root#xff0c;找出存在于 不同 节点 A 和 B 之间的最大值 V#xff0c;其中 V |A.val - B.val|#xff0c;且 A 是 B 的祖先。#xff08;如果 A 的任何子节点之一为 BLeetCode 给定二叉树的根节点 root找出存在于 不同 节点 A 和 B 之间的最大值 V其中 V |A.val - B.val|且 A 是 B 的祖先。如果 A 的任何子节点之一为 B或者 A 的任何子节点是 B 的祖先那么我们认为 A 是 B 的祖先 示例 1 输入root [8,3,10,1,6,null,14,null,null,4,7,13]
输出7
解释
我们有大量的节点与其祖先的差值其中一些如下
|8 - 3| 5
|3 - 7| 4
|8 - 1| 7
|10 - 13| 3
在所有可能的差值中最大值 7 由 |8 - 1| 7 得出。 示例 2 输入root [1,null,2,null,0,3]
输出3 方法一「递」
V∣A.val−B.val∣要是V尽可能的大分类讨论 ① 如果 A.val B.val 那么 A.val 越小V 越大 ② 如果 A.val B.val 那么 A.val 越大V 越大
故无需记录递归路径中的全部节点值只需记录递归路径中的最小值 minV 和 最大值 maxV - minV min(minV,B.val); - maxV max(maxV,B.val);
每递归到一次节点B计算 max(∣minV−B.val∣,∣maxV−B.val∣)
由于 minV B.val maxV 上式可化简为max(B.val−minV,maxV−B.val)
并更新答案的最大值ans max(ans,max(B.val - minV,maxV - B.val));
// 方法一自顶向下
class Solution {
public:int ans 0;void dfs(TreeNode* node,int minV,int maxV) {if(node nullptr) return;minV min(minV,node-val);maxV max(maxV,node-val);ans max(ans,max(node-val - minV,maxV - node-val));dfs(node-left,minV,maxV);dfs(node-right,minV,maxV);}int maxAncestorDiff(TreeNode* root) {dfs(root, root-val, root-val);return ans;}
}; 优化对于一条从根出发向下的路径实际上算的是这条路径上任意两点的最大差值
递归到叶子时minV 和 maxV是从根到叶子的路径上的最小值和最大值那么从根到叶子的路径上任意两点的最大差值maxV - minV 。所以无需每个节点都去更新答案在递归到终点时才去更新答案
// 方法一自顶向下
class Solution {
public:int ans 0;void dfs(TreeNode* node,int minV,int maxV) {if(node nullptr) {ans max(ans,maxV-minV);return;}minV min(minV,node-val);maxV max(maxV,node-val);dfs(node-left,minV,maxV);dfs(node-right,minV,maxV);}int maxAncestorDiff(TreeNode* root) {dfs(root, root-val, root-val);return ans;}
};
方法二「归」 int minVnode-val,maxVminV;
minV min(minV,min(minLV,minRV));
maxV max(maxV,max(maxLV,maxRV));
ans max(ans,max(node-val - minV,maxV - node-val));
// 自底向上
class Solution {
public:int ans 0;pairint,int dfs(TreeNode* node) {if(node nullptr) return {INT_MAX, INT_MIN};int minVnode-val,maxVminV;auto [minLV,maxLV] dfs(node-left); auto [minRV,maxRV] dfs(node-right);minV min(minV,min(minLV,minRV));maxV max(maxV,max(maxLV,maxRV));ans max(ans,max(node-val - minV,maxV - node-val));return {minV,maxV};}int maxAncestorDiff(TreeNode* root) {dfs(root);return ans;}
};
参考和推荐文章
1026. 节点与其祖先之间的最大差值 - 力扣LeetCodehttps://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/solutions/2232367/liang-chong-fang-fa-zi-ding-xiang-xia-zi-wj9v/
