题目概述(简单难度)

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例3：

输入：root = []
输出：true

题目链接：

点我进入leetcode

思路与代码

思路1

这道题目的思路也是非常简单的：

平衡二叉树如果要平衡，一定是每个节点的高度差的绝对值不能超过1

所以这道题目的思路是这样的:

1:首先判断当前节点的左树和有树的高度差是否小于等于1

2:然后再判断这个节点的左树是否平衡

3:然后再判断这个节点的右树是否平衡

具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程

这里需要用到递归以及求高度的函数.

代码1

class Solution {
    public int getHeight(TreeNode node) {
        if(node == null) {
            return 0;
        }
        int leftheight = getHeight(node.left);
        int rightheight = getHeight(node.right);
        return leftheight > rightheight ?
                leftheight + 1 : rightheight + 1;
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        //注意是三个条件都要同时满足，使用逻辑与
        return Math.abs(leftHeight-rightHeight) <= 1 
        && isBalanced(root.left) && isBalanced(root.right);
    }
}

我之前的问题是把这三个都要满足的条件分开进行了判断，没有使用逻辑与，总有测试用例过不去.

对于这份代码：

其时间复杂度为O(N 2 N^{2}N

2

),因为对于每一个节点求其高度的空间复杂度为O(N）,一共有N个节点，所以时间复杂度为O(N 2 N^{2}N

2

）

空间复杂度为O(N）其中 N是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数取决于我们的高度(或者是深度),递归调用的层数不会超过 N,最坏情况下，二叉树的高度等于节点数,所以说递归调用的层数是小于等于N的，

思路2

思路1中的代码的时间复杂度为O(N 2 N^{2}N

2

),但是我们还可以继续优化，将时间复杂度优化为O(N),具体方式如下:

代码2

class Solution {
    public int height(TreeNode node) {
        if(node == null) {
            return 0;
        }
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
      //当每次遍历完成后左子树的返回值和右子树的返回值如果都大于0，说明最终的在根节点处的返回值也一定是大于0的
        if(leftHeight >=0 && rightHeight >=0 && Math.abs(leftHeight-rightHeight) <= 1) {
            return Math.max(leftHeight,rightHeight) + 1; 
        }else {
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        if(height(root) >= 0) {
            return true;
        }
        return false;
    }
}

方法1中由于是自顶向下递归，因此对于同一个节点，函数 getHeight会被重复调用，导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，函数height只会被调用一次。

自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。

递归返回值

当节点root 左 / 右子树的高度差 < 2 ：则返回以节点root为根节点的子树的最大高度，即节点 root 的左右子树中最大高度加 1 （ max(left, right) + 1 ）；

当节点root 左 / 右子树的高度差 ≥2 ：则返回 -1，代表 此子树不是平衡树 。

递归终止条件：

当越过叶子节点时，返回高度 0 ；

当左（右）子树高度 left== -1 时，代表此子树的 左（右）子树 不是平衡树，因此直接返回 -1 ；

左右子树高度等于-1（也就是在根节点1处的时候，leftHeight和rightHeight的值此时都为-1)的情况就是如下情况:

总结下来就是当每次遍历完成后左子树的返回值和右子树的返回值如果都大于0，说明最终的在根节点处的返回值也一定是小于等于1的，假如其中左子树的返回值或者右子树的返回值的其中一个值为-1，那么最终某个根节点的返回值也一定是大于1的，那么就不是一个平衡二叉树了.

对于这个算法来说:

时间复杂度:其中 n 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，而之前的做法每个需要判断两次，所以时间复杂度为O(N 2 N^{2}N

2

),方法2中最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)。

空间复杂度:O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。

总结

考察对于二叉树的掌握，此道题目采用了两种方法来做，也是非常经典的一道题目，面试的时候建议直接做出O(N)的解法.