剑指offer三十九之平衡二叉树

时间:2021-09-04 12:01:31

一、题目

  输入一棵二叉树,判断该二叉树是否是平衡二叉树。

二、思路

详解代码。

三、代码

public class Solution {
    //判断根节点左右子树的深度,高度差超过1,则不平衡
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root==null) {
            return true;
        }
        int left = getTreeDepth(root.left);
        int right = getTreeDepth(root.right);
        return Math.abs(left-right)>1?false:true;
    }
    //求取节点的深度
    public static int getTreeDepth(TreeNode root) {
        if (root==null) {
            return 0;
        }
        int leftDepth = 1+getTreeDepth(root.left);
        int rightDepth = 1+getTreeDepth(root.right);
        return leftDepth>rightDepth?leftDepth:rightDepth;
    }
}

-----------------------------------

参考链接:

https://www.nowcoder.com/questionTerminal/8b3b95850edb4115918ecebdf1b4d222