<del id="cq00i"></del>

5030-節點與其祖先之間的最大差值

OnlyMyRailgun 發布于2019-08-19 11:39 / 1405人閱讀

摘要：前言的節點與其祖先之間的最大差值給定二叉樹的根節點，找出存在于不同節點和之間的最大值，其中，且是的祖先。提示樹中的節點數在到之間。

前言

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之間的訪問

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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