笔试面试题目：平衡二叉树的判断

article/2025/8/28 16:35:33

一. 前面的话

学如逆水行舟，不进则退。心如平原野马，易放难收。春节假期，基本结束，是该回归正常的节奏了。

生活和工作，需要平衡。紧张和松弛，亦需平衡。今天，我们来聊一个笔试面试题目：平衡二叉树的判断。

这个问题很简单，写点代码玩一下，一来是找回代码的感觉，二来是找回工作状态的感觉，经leetcode测试无误。

二. 平衡二叉树的判断

平衡二叉树，是非常基础的内容。在数据结构中，经常用到的红黑树，便是基于平衡二叉树而言的，它有很多优良的性质。那么，到底什么是平衡二叉树呢？且看leetcode题目：

那么，怎么判断一颗二叉树是否为平衡二叉树呢？直接根据上述定义判断就行。具体来说，就是：

空树是平衡二叉树
左右子树都是平衡二叉树
左右子树高度之差不大于1

显然，这是一个递归问题，用递归算法即可。顺便说一下，在求二叉树高度时，也是一个递归问题。接下来，可以直接写程序了！当然，在写程序之前，也别着急，阅读原文那里，有一个彩蛋，希望你能看到。

接下来，就是写程序了，练练手，找找感觉，如下：

func isBalanced(root *TreeNode) bool {    if root == nil {        return true    }
    gap := getAbs(treeHeight(root.Left) - treeHeight(root.Right))    if isBalanced(root.Left) && isBalanced(root.Right) && gap <= 1 {        return true    }
    return false}
func treeHeight(root *TreeNode) int {    if root == nil {        return 0    }
    if root.Left == nil && root.Right == nil {        return 1    }
    if root.Left == nil {        return treeHeight(root.Right) + 1    }
    if root.Right == nil {        return treeHeight(root.Left) + 1    }
    return getMax(treeHeight(root.Left), treeHeight(root.Right)) + 1}
func getMax(x, y int) int {    if x > y {        return x    }
    return y}
func getAbs(x int) int {    if x < 0 {        return -x    }
    return x}