首页 > 其他分享 >每日一题:1026. 节点与其祖先之间的最大差值

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

时间:2024-04-05 15:33:56浏览次数:20  
标签:node 1026 val mn mx 差值 root 节点

给定二叉树的根节点 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 得出。

我们不需要维护每个节点的最大差值,只需要维护一条路径上的最大元素和最小元素就够了,外加一个深度优先遍历。

class Solution {
public:
    int ans=0;
    void dfs(TreeNode* node,int mn,int mx){
        if(node==nullptr)return ;
        mn=min(mn,node->val);
        mx=max(mx,node->val);
        ans=max(ans,max(node->val-mn,mx-node->val));
        dfs(node->right,mn,mx);
        dfs(node->left,mn,mx);
    }
    int maxAncestorDiff(TreeNode* root) {
        dfs(root,root->val,root->val);
        return ans;
    }
};

 

标签:node,1026,val,mn,mx,差值,root,节点
From: https://www.cnblogs.com/Liubox/p/18115788

相关文章

  • 拓扑排序--有向无环图中一个节点的所有祖先
    题目描述给你一个正整数 n ,它表示一个 有向无环图 中节点的数目,节点编号为 0 到 n-1 (包括两者)。给你一个二维整数数组 edges ,其中 edges[i]=[fromi,toi] 表示图中一条从 fromi 到 toi 的单向边。请你返回一个数组 answer,其中 answer[i]是第 i 个节......
  • 删除二叉搜索树中的节点(力扣450)
    文章目录题目前知二叉搜索树是什么?题解一、思路二、解题方法三、Code总结题目Problem:450.删除二叉搜索树中的节点给定一个二叉搜索树的根节点root和一个值key,删除二叉搜索树中的key对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新......
  • 多种方法从尾部移除指定位置的链表节点
    连绵的春雨把人困在家乡,于是我继续开始刷着算法题,通过19.Remove年thNodeFromEndofList复习了一波链表的操作,这道题也是比较典型的链表问题,值得分享一下。题目如下所示:Giventheheadofalinkedlist,removethenthnodefromtheendofthelistandreturnitsh......
  • 每日一题: 2192. 有向无环图中一个节点的所有祖先
    给你一个正整数 n ,它表示一个 有向无环图 中节点的数目,节点编号为 0 到 n-1 (包括两者)。给你一个二维整数数组 edges ,其中 edges[i]=[fromi,toi] 表示图中一条从 fromi 到 toi 的单向边。请你返回一个数组 answer,其中 answer[i]是第 i 个节点的所有 祖......
  • leetcode每日一题 1379. 找出克隆二叉树中的相同节点
    问题描述给你两棵二叉树,原始树original和克隆树cloned,以及一个位于原始树original中的目标节点target。其中,克隆树cloned是原始树original的一个副本。请找出在树cloned中,与target相同的节点,并返回对该节点的引用(在C/C++等有指针的语言中返回节点指针,其他......
  • zookeeper监听集群节点的实现zkclient组件实现方案(Java版)
    ZooKeeperWatcher机制client向zookeeper注册监听client注册的同时会存储一个WatchManager对象向zookeeper发生改变则notificationclient并发送一个WatchManager对象,然后client再更新该对象packagecom.jacky.zk.demo;importorg.I0Itec.zkclient.IZkChildListen......
  • LeetCode-1379. 找出克隆二叉树中的相同节点【树 深度优先搜索 广度优先搜索 二叉树】
    LeetCode-1379.找出克隆二叉树中的相同节点【树深度优先搜索广度优先搜索二叉树】题目描述:解题思路一:递归,由于我们比较的是节点而不是节点值(例如C++比较的是地址),所以下面的代码也适用于树中有值相同节点的情况(本题的进阶问题)。解题思路二:递归这题有几个关键点,一:判......
  • AWS通过交换机连接管理节点检查AWS云状态
    1、ceph集群检查要查看Ceph集群的状态,可以使用Ceph的命令行工具ceph。以下是一个基本的命令,它将提供Ceph集群的概览状态,包括集群的健康状况、OSD数量、PG状态等:ceph-s#这个命令会输出一个详细的状态报告,其中包括了集群的各种资源和服务的状态。cephosdtree|grep-E'host|......
  • 巧用Excel计算年份间天数差值
    0.问题1.题解1.1普通思路如果正常计算需要考虑到闰年的计算,然后计算出总天数/7得到总周数(有可能是个小数,多出来的天数),之后还要知晓开始时间和结束时间是周几,要不要多计算星期一1.2使用Excel首先在开头两个单元格周输入时间,然后在第三个单元格直接输入=,然后分别选......
  • system.text.json 搜索获取节点值
    搜索Json节点值publicstaticclassJsonStringExtensions{publicstaticboolTryGetNestValueByJsonKey(thisstringjsonString,stringkey,outstringres){res=string.Empty;try{vararr=key.Split('.');......