剑指Offer——平衡二叉树

By AverageJoeWang
 标签:

平衡二叉树

  • 题目描述
    输入一棵二叉树,判断该二叉树是否是平衡二叉树。

  • 解题思路

改编自求树高代码,平衡的子树高度正常求,不平衡的直接设为-1

  • 代码实现
public class Solution {
   public boolean IsBalanced_Solution(TreeNode root) {
        return cheat(root) >= 0;
    }

    public int cheat(TreeNode root) {
        if (root == null) return 0;
        int left = cheat(root.left);
        int right = cheat(root.right);
        return (left >= 0 && right >= 0 && Math.abs(left - right) <= 1) ? 1 + Math.max(left, right) : -1;
    }
}