刷题专栏（八）：平衡二叉树

前言

最近要和二叉树死磕到底了，必须把二叉树相关数据结构的题目全做完才行。

今天的这一道《平衡二叉树》，虽然和昨天的那一道有序数组转平衡二叉树的题目不一样，但是本质上的结构是一样的。

昨天的那道题是转换为平衡的二叉树，今天的这道题是提供一个二叉树让你判断是不是平衡的二叉树。

算法题：平衡二叉树

昨天我们处理的那一道转换平衡二叉树，是根据二分法和递归来处理的，那这一道题又怎么解决呢？

按照之前总结的规律，逢二叉树，基本都会用到递归；那么看一下这道题是不是也要用递归呢？

看来是要用的，因为要查询到所有的分支才行。

那么二叉树怎么才能算作是平衡二叉树呢？那自然是左右分支的层数一样，或者是差值为一的才能算作是平衡二叉树。

这个时候就面临一个选择，是从根节点开始一层一层的递归遍历，最后得到结果。

还有就是从最底层节点开始往根节点算起，这个时候中间可能已经判断出结果来了，就可以提前终止调递归循环。

代码展示

我们这里采用了从底层节点到根部节点的检索方式，代码如下所示：

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

执行结果：

结果不是很理想，大家可以尝试其他方式。

总结

今天是二叉树的第三道题了，明天我们接着看二叉树，欢迎大家关注刷题专栏。