[LeetCode][Java] Balanced Binary Tree

浏览数：56 / 时间：2015年06月08日

题目：

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.

题意：

给定一棵二叉树，判定它是否为平衡二叉树。

算法分析：

* 平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），
* 且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
* 并且左右两个子树都是一棵平衡二叉树。

* 下面的代码就完全按照定义，首先得到节点左右子树的高度（递归），然后判断左右子树是否为平衡二叉树，

* 利用递归完成整棵树的判断。完全满足条件，就返回true.

AC代码：

public class Solution 
{
    //递归
    public boolean isBalanced(TreeNode root)
    {
        if(root==null) return true;
        int leftdepth;
        int rightdepth;
        leftdepth=maxDepth(root.left);
        rightdepth=maxDepth(root.right);
        if(Math.abs(leftdepth-rightdepth)<=1&&isBalanced(root.left)&&isBalanced(root.right)) return true;
        else return false;
    }
    //又是递归 采用代码《Maximum Depth of Binary Tree 》--https://leetcode.com/problems/maximum-depth-of-binary-tree/
    public int maxDepth(TreeNode root) 
    {
        if(root == null)
        {  
            return 0;  
        }  
        int l = maxDepth(root.left);  
        int r = maxDepth(root.right);  
        return l > r? l + 1:r+ 1; 
    }
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

[LeetCode][Java] Balanced Binary Tree