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

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) {
        // 调用辅助函数，如果返回值为-1，说明不平衡，否则为平衡
        return depth(pRoot) != -1;
    }
    
    /**
     * 辅助方法：返回树的高度，如果树不平衡返回-1
     */
    private int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = depth(root.left);  // 左子树的深度
        if (left == -1) {  // 如果左子树不平衡，直接返回-1
            return -1;
        }

        int right = depth(root.right);  // 右子树的深度
        if (right == -1) {  // 如果右子树不平衡，直接返回-1
            return -1;
        }

        if (Math.abs(left - right) > 1) {  // 如果左右子树深度差超过1，返回-1
            return -1;
        }

        return Math.max(left, right) + 1;  // 返回当前树的深度
    }
}


//这种方法每个节点只被访问一次，因此时间复杂度是O(n)。而且我们没有使用额外的数据结构，因此空间复杂度是O(1)。

平衡二叉树的判断要满足两个条件：首先它自己是一个平衡二叉树，并且它的左右子树也都是平衡二叉树。

为了达到题目要求的时间复杂度和空间复杂度，我们可以使用自底向上的策略。首先判断子树是不是平衡，然后再通过子树的结果来判断当前树是否平衡。此外，为了不重复计算，当我们在计算树的高度时，可以在同一个递归过程中判断树是否平衡。

具体思路如下：

1.对于一个节点，我们递归地判断其左子树和右子树的高度差是否不超过 1，并且左子树和右子树也都是平衡的。

2.如果上述条件都满足，则该树是平衡的；否则，不是。