Go语言实现：【剑指offer】平衡二叉树
2024-10-08 05:44:55
该题目来源于牛客网《剑指offer》专题。
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/
2 2
/
3 3
/
4 4
返回 false 。
Go语言实现：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isBalanced(root *TreeNode) bool {
if root == nil {
return true
}
return math.Abs(float64(maxDepth(root.Left)) - float64(maxDepth(root.Right))) <= 1 &&
isBalanced(root.Left) && isBalanced(root.Right)
}
//最大深度
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
} else {
left := maxDepth(root.Left)
right := maxDepth(root.Right)
if left > right {
return 1 + left
} else {
return 1 + right
}
}
}
最新文章
- Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)D Dense Subsequence
- 《Linux内核设计与实现》CHAPTER13阅读梳理
- 看懂UML类图
- MySQL(五) MySQL中的索引详讲
- Linux探秘之I/O效率
- 锋利的jQuery-5--下拉框的应用（看写法）
- LA 3213 Ancient Cipher
- 怎么用visual studio2010编写c++程序
- 使用simhash库来进行网页去重
- JavaScript技巧(未完成)
- 2018-2019-1 20189210 《LInux内核原理与分析》第四周作业
- 数组复制的五种方式（遍历循环一一赋值、System.arraycopy、地址赋值、克隆clone()、Arrays.copyof()）
- 2017-2018-2 20155303 『网络对抗技术』Exp3：免杀原理与实践
- C#中引用第三方ocx控件引发的问题以及解决办法
- shell for if
- 一文掌握Docker Compose
- python数据类型之集合
- type="submit"表单提交理解
- 2018 Multi-University Training Contest 7 Solution
- 移动端html5页面导航栏悬浮遮挡内容第一行解决办法