LeetCode 110 Balanced Binary Tree 平衡二叉樹

anquan 發(fā)布于2019-08-16 13:28 / 2152人閱讀

摘要：題意判斷一顆二叉樹是否是平衡二叉樹，平衡二叉樹的定義為，每個節(jié)點的左右子樹深度相差小于這是和求最大深度的結合在一起，可以考慮寫個函數(shù)找到拿到左右子樹的深度，然后遞歸調(diào)用函數(shù)判斷左右子樹是否也是平衡的，得到最終的結果。

LeetCode 110 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.
題意：
判斷一顆二叉樹是否是平衡二叉樹，平衡二叉樹的定義為，每個節(jié)點的左右子樹深度相差小于1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

Return false.

Solution 1：
這是和求最大深度的結合在一起，可以考慮寫個helper函數(shù)找到拿到左右子樹的深度，然后遞歸調(diào)用isBalanced函數(shù)判斷左右子樹是否也是平衡的，得到最終的結果。時間復雜度O(n^2)

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftDep = depthHelper(root.left);
        int rightDep = depthHelper(root.right);
        if (Math.abs(leftDep - rightDep) <= 1 && isBalanced(root.left) && isBalanced(root.right)) {
            return true;
        }
        return false;
    }
    private int depthHelper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(depthHelper(root.left), depthHelper(root.right)) + 1;
    }

Solution 2：
解題思路：
再來看個O(n)的遞歸解法，相比上面的方法要更巧妙。二叉樹的深度如果左右相差大于1，則我們在遞歸的helper函數(shù)中直接return -1，那么我們在遞歸的過程中得到左子樹的深度，如果=-1，就說明二叉樹不平衡，也得到右子樹的深度，如果=-1，也說明不平衡，如果左右子樹之差大于1，返回-1，如果都是valid，則每層都以最深的子樹深度+1返回深度。

    public boolean isBalanced(TreeNode root) {
        return dfsHeight(root) != -1;
    }
    //helper function, get the height
    public int dfsHeight(TreeNode root){
        if (root == null) {
            return 0;
        }
        int leftHeight = dfsHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = dfsHeight(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }

云服務器 GPU云服務器平衡二叉樹平衡二叉樹課程設計 binary-tree binary-search-tree

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

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

[Leetcode] Balanced Binary Tree 平衡二叉樹

摘要：在遞歸中，從葉子結點開始一層層返回高度，葉子結點是。我們返回代表非平衡，返回自然數(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...

lylwyy2016 2019-08-14 12:23 評論0 收藏0
[LintCode/LeetCode] Balanced Binary Tree

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

morgan 2019-08-14 15:33 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

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

warmcheng 2019-08-26 10:09 評論0 收藏0
前端 | 每天一個 LeetCode

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

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

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

tain335 2019-08-26 10:28 評論0 收藏0