平衡二叉树

题目

给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两个子树的深度相差不会超过1。 http://www.lintcode.com/zh-cn/problem/balanced-binary-tree/

分析

只要实现一个求给定节点开始到叶子节点的高度函数,这道题目就迎刃而解。对于任意一个节点,若它的左右子树均为平衡二叉树,且左右子树的高度差不超过1,那么它就是平衡二叉树。不能遗漏左右子树是否为平衡二叉树的判断,否则可能出现左右子树高度相差不超过1,但其实左子树或者右子树存在某一节点不平衡的情况。

代码


/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 * 
 * 
 */


public class Solution {
    
    int height(TreeNode root){
        if(root == null) return 0;
        int hl = this.height(root.left);
        int hr = this.height(root.right);
        return (hl > hr ? hl : hr) + 1;
    }
    /*
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    public boolean isBalanced(TreeNode root) {
        // write your code here
        if(root == null) return true;
        
        if( this.isBalanced(root.left) && this.isBalanced(root.right) ){
            int hl = this.height(root.left);
            int hr = this.height(root.right);
            if( hl == hr || hl+1==hr || hl==hr+1 ){
                return true;
            }
            return false;
        }else{
            return false;
        }
        
    }
}
Show Comments

Get the latest posts delivered right to your inbox.