成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Balanced Binary Tree 平衡二叉樹

lylwyy2016 / 1455人閱讀

摘要：在遞歸中，從葉子結(jié)點(diǎn)開始一層層返回高度，葉子結(jié)點(diǎn)是。我們返回代表非平衡，返回自然數(shù)代表有效的子樹高度。

Balanced Binary Tree 
Given a binary tree, determine if it is height-balanced.


For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
深度優(yōu)先搜索 復(fù)雜度

時間 O(N) 空間 O(h) 遞歸?？臻g

思路

非平衡的條件是有兩個葉子節(jié)點(diǎn)的深度相差大于1，最直接的想法就是把左子樹和右子樹的高度都算出來，如果相差大于1則說明不是平衡的。在遞歸中，從葉子結(jié)點(diǎn)開始一層層返回高度，葉子結(jié)點(diǎn)是1。我們返回-1代表非平衡，返回自然數(shù)代表有效的子樹高度。

代碼 
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        int left = findHeight(root.left);
        int right = findHeight(root.right);
        return left != -1 && right != -1 && Math.abs(left-right)<=1;
    }
    
    private int findHeight(TreeNode root){
        if(root == null) return 0;
        int left = findHeight(root.left);
        int right = findHeight(root.right);
        if(left == -1 || right == -1 || Math.abs(left-right) > 1) return -1;
        return Math.max(left, right)+1;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64443.html

相關(guān)文章

  • LeetCode 110 Balanced Binary Tree 平衡二叉樹

    摘要：題意判斷一顆二叉樹是否是平衡二叉樹，平衡二叉樹的定義為，每個節(jié)點(diǎn)的左右子樹深度相差小于這是和求最大深度的結(jié)合在一起，可以考慮寫個函數(shù)找到拿到左右子樹的深度，然后遞歸調(diào)用函數(shù)判斷左右子樹是否也是平衡的，得到最終的結(jié)果。 LeetCode 110 Balanced Binary Tree Given a binary tree, determine if it is height-bala...

    anquan 評論0 收藏0

  • [LintCode/LeetCode] Balanced Binary Tree

    摘要：根據(jù)二叉平衡樹的定義，我們先寫一個求二叉樹最大深度的函數(shù)。在主函數(shù)中，利用比較左右子樹的差值來判斷當(dāng)前結(jié)點(diǎn)的平衡性，如果不滿足則返回。 Problem Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as...

    morgan 評論0 收藏0

  • 前端 | 每天一個 LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

    張漢慶 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

    摘要：微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...

    warmcheng 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...

    tain335 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<