二叉树的层序遍
解题思路&题解
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| func levelOrder(root *TreeNode) [][]int {
ret := [][]int{}
if root == nil {
return ret
}
q := []*TreeNode{root}
for i := 0; len(q) > 0; i++ {
ret = append(ret, []int{})
p := []*TreeNode{}
for j := 0; j < len(q); j++ {
node := q[j]
ret[i] = append(ret[i], node.Val)
if node.Left != nil {
p = append(p, node.Left)
}
if node.Right != nil {
p = append(p, node.Right)
}
}
q = p
}
return ret
}
type Queue []*TreeNode
func (q *Queue) Add(data *TreeNode) bool {
*q = append(*q, data)
return true
}
func (q *Queue) Remove() *TreeNode {
node := (*q)[0]
*q = (*q)[1:]
return node
}
func (q *Queue) isEmpty() bool {
if len(*q) == 0 {
return true
}
return false
}
|
二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
1
2
3
4
5
6
7
| 给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
|
解题思路&题解
简单的通过递归，在返回的时候判断左子树深还是右子树深，然后返回比较深的那颗子树的值。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
| func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
leftDeep := maxDepth(root.Left) + 1
rightDeep := maxDepth(root.Right) + 1
if leftDeep >= rightDeep {
return leftDeep
} else {
return rightDeep
}
}
|
对称二叉树
解题思路&题解
和判断深度差不多，也是分为左子树和右子树。通过交叉传入左右子树判断节点的值是否相等。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
| func isSymmetric(root *TreeNode) bool {
return check(root, root)
}
func check(p, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil {
return false
}
return p.Val == q.Val && check(p.Left, q.Right) && check(p.Right, q.Left)
}
|