笔试面试题目：平衡二叉树的判断
一. 前面的话
学如逆水行舟，不进则退。心如平原野马，易放难收。春节假期，基本结束，是该回归正常的节奏了。
生活和工作，需要平衡。紧张和松弛，亦需平衡。今天，我们来聊一个笔试面试题目：平衡二叉树的判断。
这个问题很简单，写点代码玩一下，一来是找回代码的感觉，二来是找回工作状态的感觉，经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
}经在leetcode上进行自测，正确无误，符合预期。
三. 最后的话
这篇文章很简单，就当是从春节假期到工作的一个过渡文章吧。再次，祝大家生活工作平衡，就像本文所说的平衡二叉树一样。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-04-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
