题目主要信息

1、输入一棵节点数为n的二叉树，判断该二叉树是否是平很二叉树

2、我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

方法一：自顶向下递归

具体方法

可以使用前序遍历，分别计算左右子树的高度，如果左右高度差不超过1，在分别递归遍历左右子树，判断左子树和右子树是否平衡。从根节点层层向下的遍历计算。

Java代码

import java.util.*;
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        //可以分别求出左右子树的高度，然后进行对比
        if(root == null) return true;
        if(Math.abs(TreeDepth(root.left)-TreeDepth(root.right))>1) return false;
        return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
    }
    //求二叉树深度的方法
    public int TreeDepth(TreeNode root) {
        //说明已经到叶子节点了
        if(root == null) return 0;
        //递归求左子树的高度
        int left_height = TreeDepth(root.left);
        //递归求右子树的高度
        int right_height = TreeDepth(root.right);
        return (left_height>right_height)?(left_height+1):(right_height+1);
    }
}

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，n表示树的节点个数
• 空间复杂度：$O(n)O(n)$，递归的深度不会超过$nn$

方法二：自底向上递归

具体方法

在方法一中，从上到下计算，存在重复计算的过程，时间复杂度过高。

自底向上类似后序遍历，对当前节点，先递归遍历判断左右子树是否平衡，在判断当前节点为根的子树是否平衡。如果一棵子树是平衡的，就返回其高度，否则返回-1。如果一个子树不平衡，则整个二叉树都不平衡。

java

import java.util.*;
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        //可以分别求出左右子树的高度，然后进行对比
        return TreeDepth(root) >= 0;
    }
    //求二叉树深度的方法
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = TreeDepth(root.left);
        int rightHeight = TreeDepth(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，其中 n 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是$O(n)O(n)$。
• 空间复杂度：$O(n)O(n)$，其中 n是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过$nn$。