5030-节点与其祖先之间的最大差值

OnlyMyRailgun 发布于2019-08-19 11:39 / 1404人阅读

摘要：前言的节点与其祖先之间的最大差值给定二叉树的根节点，找出存在于不同节点和之间的最大值，其中，且是的祖先。提示树中的节点数在到之间。

前言

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) {
        Queue queue = 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;
    }

云服务器 GPU云服务器 js中日期差值的计算祖先共有祖先元素 linux之间的访问

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77616.html

mongodb简介

摘要：示例给追加别名，用法作用加一个值到数组内，而且只有当这个值在数组中不存在时才增加。示例删除记录内的所有别名可以看到和已经全部被删除了用法作用对字段进行重命名示例把记录的字段重命名为由结果可以看出字段已经被更新为了。 1. 来源存储方式就是个大json，很灵活。 2. 官网下载安装 https://docs.mongodb.com 3. 启动 // 指定数据库所在的文件夹 mongod...

zsirfs 2019-06-26 17:17 评论0 收藏0
CSS概念【记录】

摘要：语法规则注释层叠优先级继承值块格式化上下文盒模型层叠上下文可替换元素外边距合并包含块视觉格式化模型布局模式语法属性值声明声明块规则规则集规则规则一个语句定义样式表使用的字符集告诉引擎引入一个外部样式表嵌套规则如果满足媒介查询的条件则条件规则 1、CSS语法 2、@规则 3、注释 4、层叠 5、优先级 6、继承 7、值 8、块格式化上下文 9、盒模型 10、层叠上下文 11、可替换元素 12、...

番茄西红柿 2019-04-23 11:55 评论0 收藏0
CSS那些事

摘要：今天跟大家分享一下中一些比较重要和比较容易被忽略的东西，开始吧。当为时，块级元素的宽度会填满整个包含块。也就是说上下外边距的值也是以父元素的宽度为标准的。今天跟大家分享一下CSS中一些比较重要和比较容易被忽略的东西，开始吧。样式优先级当你在不同地方不同的选择器中对同一个元素属性添加了不同的样式的时候，该如何判断最后哪个样式会作用到元素上呢？判断的依据就是样式的优先级。样式优先...

LinkedME2016 2019-08-28 17:56 评论0 收藏0
图说 Firefox 全新 CSS 引擎

摘要：的主要组件包含了一个全新的引擎，称为量子，也称为。这个新引擎集成了四种不同浏览器的最新创新技术，创造出一个全新的超级引擎。这可以发生在多个图层上。最终，拥有最高特异性的规则会胜出。原文：Inside a Super Fast CSS Engine: Quantum CSS(Aka Stylo), Lin Clark 注：原文发布于 2017 年 8 月，本文翻译于 2018 年 4 ...

lsxiao 2019-08-29 15:06 评论0 收藏0