真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

LeetCode如何檢查二叉樹的平衡性

這篇文章主要為大家展示了“LeetCode如何檢查二叉樹的平衡性”，內(nèi)容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“LeetCode如何檢查二叉樹的平衡性”這篇文章吧。

專注于為中小企業(yè)提供成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計服務(wù),電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)魏縣免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了近千家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。

1，問題簡述

實現(xiàn)一個函數(shù)，檢查二叉樹是否平衡。

在這個問題中，平衡樹的定義如下：

任意一個節(jié)點，其兩棵子樹的高度差不超過 1。

2，示例

示例 1:給定二叉樹 [3,9,20,null,null,15,7]    3   / \  9  20    /  \   15   7返回 true 。示例 2:給定二叉樹 [1,2,2,3,3,null,null,4,4]      1     / \    2   2   / \  3   3 / \4   4返回 false 。

3，題解思路

根據(jù)遞歸方式進(jìn)行解決

4，題解程序


public class IsBalancedTest {    public static void main(String[] args) {        TreeNode t1 = new TreeNode(3);        TreeNode t2 = new TreeNode(9);        TreeNode t3 = new TreeNode(20);        TreeNode t4 = new TreeNode(15);        TreeNode t5 = new TreeNode(7);        t1.left = t2;        t1.right = t3;        t3.left = t4;        t3.right = t5;        boolean balanced = isBalanced(t1);        System.out.println("balanced = " + balanced);
    }
    public static boolean isBalanced(TreeNode root) {        if (root == null) {            return true;        }        int leftDepth = dfs(root.left);        int rightDepth = dfs(root.right);        int abs = Math.abs(leftDepth - rightDepth);        if (abs <= 1 && isBalanced(root.left) && isBalanced(root.right)) {            return true;        }        return false;    }
    private static int dfs(TreeNode root) {
        if (root == null) {            return 0;        }        return Math.max(dfs(root.left), dfs(root.right)) + 1;    }}