平衡二叉树

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

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

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

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

初次分析

首先判断左右子树是否为空，如果有一个为空，另一个不为空，则即为1。继续迭代遍历不为空的子树，如果他的左右子树存在，则认为不是平衡二叉树。

这种方法只能测量出来连续两层的子树是否是平衡二叉树，而不能从左右两边整体的判断是否是平衡二叉树。

所以需要增加一个条件，先整体的判断左右子树最大高度差，如果不超过2，则从上到下，分别判断左右子树的高度差。

如果不是平衡二叉树，则一定存在一个子树不是平衡二叉树或者整体的高度差大于2。

例如

其左子树的高度差大于2，符合第一种情况，所以不是平衡二叉树。

再比如

左子树是个平衡二叉树，但是左子树和右子树的高度差大于二，符合第二种情况，所以这个二叉树从整体上看也不是平衡二叉树。

public static boolean isBalanced(TreeNode root) {
    if(root==null){
            return true;
        }
        return  (Math.abs(deep(root.left) - deep(root.right)) <= 1)&& isBalanced(root.left) && isBalanced(root.right);
    }
​
    public static int deep(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.max(deep(root.left)+1,deep(root.right)+1);
    }

继续分析

时间复杂度: O(n2)，首先需要一次深度递归，递归出左右子树的深度，然后就是左右子树的递归，左右子树递归的过程又会继续递归左右子树的深度。不难发现，有很多重复的过程。换个思路，从上往下会重复，那么从下往上呢？

递归到最后一层叶子节点的时候，标记深度为0。那么叶子节点的根节点就是左右子节点的深度最大值+1，当这个最大值+1大于2之后，则认为这个子树不是平衡二叉树，那么这整个树自然也不是平衡二叉树。

答案

public static boolean isBalanced(TreeNode root) {   
    return deep(root) >= 0;
    }
public int deep(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = deep(root.left);
    int right = deep(root.right);
    if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
        return -1;
    } else {
        return Math.max(left, right) + 1;
    }
}

复杂度

• 时间复杂度: O(n)，其中 n 是二叉树中的节点个数。最坏的情况就是满二叉树，所有节点都会遍历。
• 空间复杂度：O(n)，递归调用占用的栈空间，其中n就是二叉树的个数。

总结

第一种方法类似二叉树的前序遍历，即根左右，先判断根节点的左右子树深度差，再分别判断左右子树。

而第二种方法类似二叉树的后序遍历，即左右根，先判断子树，再往上进行判断。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！