题解 | #判断是不是平衡二叉树#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    // public boolean IsBalanced_Solution (TreeNode pRoot) {
    //     if (pRoot == null) return true;
    //     if(Math.abs(reverse(pRoot.left) - reverse(pRoot.right)) >1) return false;
    //     return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)  ;

    // }

    // public int reverse(TreeNode root) {
    //     if (root == null) return 0;
    //     int left = reverse(root.left);
    //     int right = reverse(root.right);
    //     return Math.max(left, right) + 1;
    // }

    public boolean IsBalanced_Solution (TreeNode root) {
        if (root == null) return true;
        return reverse(root) > 0;

    }
    //求二叉树深度
    public int reverse(TreeNode root) {
        if (root == null) return 0;
        int left = reverse(root.left);
        int right = reverse(root.right);
        //后序遍历，在此处进行判断
        if(left == -1 || right == -1 || Math.abs(left - right) > 1){
            return -1;
        }else{
            return Math.max(left, right) + 1;
        }
    }
}

思路：

方法1：思路有点绕，先求给出的根节点是否符合平衡二叉树条件，如果不满足，直接返回false。如果为true，对左右子树再进行递归判断。判断是否是平衡二叉树，使用后序遍历，先将左右子树的高度求出来，再求绝对值是否超过1.

方法2：只需使用一次递归，使用后序遍历再求出左右子树最大深度就在后序遍历位置进行判断，巧妙的是如果不符合条件，返回-1左右失败标记。