golang刷leetcode 技巧（21）平衡二叉树
golang刷leetcode 技巧（21）平衡二叉树
golangLeetcode
发布于 2022-08-02 18:42:21
发布于 2022-08-02 18:42:21
文章被收录于专栏：golang算法架构leetcode技术php
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过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 。
限制：
1 <= 树的结点个数 <= 10000
解题思路：
1，对于树一类问题，我们优先想倒递归
2，平衡二叉树是左右子树高度差不超过1
3，那么，包含两个子问题：
A，左子树高度和右子树高度相差不超过1
B，左右子树都是平衡的
4，注意，计算高度的时候，是左右子树的大者＋1
代码实现
/**
* 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
}
l:=height(root.Left)
r:=height(root.Right)
if l>r+1 || l+1<r{
return false
}
return isBalanced(root.Left)&&isBalanced(root.Right)
}
func height(root*TreeNode)int{
if root==nil{
return 0
}
l:=height(root.Left)
r:=height(root.Right)
if l>r{
return l+1
}
return r+1
}golang 知识积累
通常在for循环中，使用break可以跳出循环，但是注意在go语言中，for select配合时，break并不能跳出循环。
package main
import (
"fmt"
"time"
)
func main() {
c := make(chan bool)
go testSelectFor(c)
c <- true
c <- false
close(c)
time.Sleep(time.Duration(2) * time.Second)
fmt.Println("Hello, 世界")
}
func testSelectFor(chExit chan bool) {
for {
select {
case v, ok := <-chExit:
if !ok {
fmt.Println("close channel 1", v)
break
}
fmt.Println("ch1 val =", v)
}
}
fmt.Println("exit testSelectFor")
}
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-03-04，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读
腾讯云开发者
