LeetCode110-Balanced Binary Tree-蒲公英云

LeetCode110-Balanced Binary Tree

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.

问题来源： https://leetcode.com/problems/balanced-binary-tree/

问题的大概意思是给一个二叉树，判断该树是否为平衡二叉树（平衡二叉树的判断条件：左右子树的高度相差最大不超过1）。

解题思路：通过递归找出每一个二叉树的左右子树的高度，然后比较左右子树高度差是否不超过1。注意若该树为空也满足条件。

源代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(null==root){
            return true;
        }
        else{
            return isBalancedTree(root);
        }
    }
    private boolean isBalancedTree(TreeNode node){
        if(null==node){
            return true;
        }
        else{
            int leftChildHeight = getHeight(node.left);
            int rightChildHeight = getHeight(node.right);
            return (Math.abs(leftChildHeight-rightChildHeight)<=1) && isBalancedTree(node.left) && isBalancedTree(node.right);
        }
    }
    private int getHeight(TreeNode node){
        if(null==node){
            return 0;
        }
        else{
            int leftChildHeight = getHeight(node.left);
            int rightChildHeight = getHeight(node.right);
            return (leftChildHeight >= rightChildHeight) ? leftChildHeight+1 : rightChildHeight+1;
        }
    }
}