摘要:前言的节点与其祖先之间的最大差值给定二叉树的根节点,找出存在于不同节点和之间的最大值,其中,且是的祖先。提示树中的节点数在到之间。
前言
Weekly Contest 132的 节点与其祖先之间的最大差值:
解题思路给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间的最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。
(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先)
示例:
输入:[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 到 5000 之间。
每个节点的值介于 0 到 100000 之间。
本题需要将问题分解一下,首先先实现根节点与每个节点的差值的最大值的算法,然后只需要遍历每个子树即可。
实现代码/** * 5030. 节点与其祖先之间的最大差值 * @param root * @return */ public int maxAncestorDiff(TreeNode root) { Queuequeue = new LinkedList<>(); queue.add(root); int max=0; while(!queue.isEmpty()){//层序遍历 TreeNode node=queue.poll(); max=Math.max(max,getMaxDiffByRoot(node)); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } return max; } /** * 获取某个根节点下所有节点与根节点的差值的最大值 * 这里选择使用层序遍历 * @param root * @return */ private int getMaxDiffByRoot(TreeNode root){ Queue queue = new LinkedList<>(); queue.add(root); //根节点的值,用于比较 int rootValue=root.val; //最大差值 int max=0; while(!queue.isEmpty()){//层序遍历每个节点 TreeNode node=queue.poll(); // 获取最大值 max=Math.max(max,Math.abs(node.val-rootValue)); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } return max; }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/77616.html
摘要:今天跟大家分享一下中一些比较重要和比较容易被忽略的东西,开始吧。当为时,块级元素的宽度会填满整个包含块。也就是说上下外边距的值也是以父元素的宽度为标准的。 今天跟大家分享一下CSS中一些比较重要和比较容易被忽略的东西,开始吧。 样式优先级 当你在不同地方不同的选择器中对同一个元素属性添加了不同的样式的时候,该如何判断最后哪个样式会作用到元素上呢?判断的依据就是样式的优先级。样式优先...
摘要:的主要组件包含了一个全新的引擎,称为量子,也称为。这个新引擎集成了四种不同浏览器的最新创新技术,创造出一个全新的超级引擎。这可以发生在多个图层上。最终,拥有最高特异性的规则会胜出。 原文:Inside a Super Fast CSS Engine: Quantum CSS(Aka Stylo), Lin Clark 注:原文发布于 2017 年 8 月,本文翻译于 2018 年 4 ...
阅读 3109·2023-04-26 01:30
阅读 638·2021-11-08 13:15
阅读 1699·2021-09-24 10:35
阅读 915·2021-09-22 15:41
阅读 1904·2019-08-30 15:44
阅读 560·2019-08-30 13:22
阅读 979·2019-08-30 13:06
阅读 1160·2019-08-29 13:22