04.树
# 01.树的遍历
# 1.1 生成树结构
- 1.前序遍历: DBACEGF(根节点排最先,然后同级先左后右)
- 2.中序遍历: ABCDEFG (先左后根最后右)
- 3.后序遍历: ACBFGED (先左后右最后根)
# 1.1.1 python
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 1.1.2 golang
package main
import "fmt"
type TreeNode struct {
Val string
Left *TreeNode // 左子树
Right *TreeNode // 右子树
}
func main() {
root := TreeNode{
Val: "D",
Left: &TreeNode{
Val: "B",
Left: &TreeNode{
Val: "A",
},
Right: &TreeNode{
Val: "C",
},
},
Right: &TreeNode{
Val: "E",
Right: &TreeNode{
Val: "G",
Left: &TreeNode{
Val: "F",
},
},
},
}
fmt.Println(root)
}
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
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
# 1.2 先根遍历
# 1.2.1 python
- 前序遍历: DBACEGF(根节点排最先,然后同级先左后右)
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def preTraverse(root):
'''
前序遍历
'''
if root==None:
return
print(root.value) # 打印当前根节点的值
preTraverse(root.left) # 只要有左孩子就一直递归
preTraverse(root.right)
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
print('前序遍历:')
preTraverse(root) # DBACEGF
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
先根遍历步骤推演
前序排列原理:
#####此时执行preTraverse(root.left) 函数
'''
1、第一步 root=Node(D) print D,D入栈[D]
2、第二步 root=Node(D).left=Node(B) print B, B入栈[D,B]
3、第三步 root=Node(B).left=Node(A) print A, A入栈[D,B,A]
4、第四步 root=Node(A).left=None,没有进入递归,顺序执行preTraverse(root.right)
5、第五步 Node(A).right==None,也没有进入递归,此时preTraverse(A) 函数才会正真返回,A出栈[D,B]
6、第六步 A的上级调用函数为:preTraverse(B.left),所以接着会顺序执行preTraverse(B.right),B的左右节点访问后B出栈[D]
7、第七步 Node(B).right==Node(C) print C,C入栈[D,C]
8、第八步 Node(C).left==None, Node(C).right==None,访问完C的左右节点后函数返回C出栈,返回上级调用[D]
9、第九步 此时返回上级调用执行preTraverse(D.right)=Node(E) print E,D出栈,E入栈[E]
'''
'''此时输出结果:DBACE'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 1.2.2 golang
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode // 左子树
Right *TreeNode // 右子树
}
func preorderTraversal(root *TreeNode) []int {
vals := []int{} // 使用列表vals存放树中数据
var preorder func(*TreeNode)
preorder = func(node *TreeNode) {
if node == nil {
return
}
vals = append(vals, node.Val) // 将根节点值添加到列表中
preorder(node.Left) // 只要有左孩子就一直递归
preorder(node.Right)
}
preorder(root)
return vals
}
func main() {
root := TreeNode{
Val: 1,
Right: &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 3,
},
},
}
vals := preorderTraversal(&root)
fmt.Println(vals) // [1 2 3]
}
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
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
# 1.3 中根遍历
# 1.3.1 python
- ABCDEFG (先左后根最后右)
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def midTraverse(root):
'''
中序遍历
'''
if root == None:
return
midTraverse(root.left) # 只要有左孩子就一直递归(这样第一个打印的就是最左边的孩子)
print(root.value)
midTraverse(root.right)
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
print('中序遍历:')
midTraverse(root) # ABCDEFG (先左后根最后右)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 1.3.2 golang
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode // 左子树
Right *TreeNode // 右子树
}
func inorderTraversal(root *TreeNode) (res []int) {
var inorder func(node *TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left) // 只要有左孩子就一直递归(这样第一个打印的就是最左边的孩子)
res = append(res, node.Val)
inorder(node.Right)
}
inorder(root)
return
}
func main() {
root := TreeNode{
Val: 1,
Right: &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 3,
},
},
}
vals := inorderTraversal(&root)
fmt.Println(vals) // [1 3 2]
}
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
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
# 1.4 后根遍历
# 14.1 python
- 后序遍历: ACBFGED (先左后右最后根)
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def afterTraverse(root):
'''
后序遍历
'''
if root == None:
return
afterTraverse(root.left) # 只要有左孩子就一直递归
afterTraverse(root.right)
print(root.value)
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
print('后序遍历:')
afterTraverse(root) # ACBFGED
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 1.4.2 golang
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode // 左子树
Right *TreeNode // 右子树
}
func postorderTraversal(root *TreeNode) (res []int) {
var postorder func(*TreeNode)
postorder = func(node *TreeNode) {
if node == nil {
return
}
postorder(node.Left) // 只要有左孩子就一直递归
postorder(node.Right)
res = append(res, node.Val)
}
postorder(root)
return
}
func main() {
root := TreeNode{
Val: 1,
Right: &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 3,
},
},
}
vals := postorderTraversal(&root)
fmt.Println(vals) // [3 2 1]
}
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
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
# 1.5 分层打印二叉树
# 1.5.1 python
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left # 左子树
self.right = right # 右子树
def layer(root):
curLayer = [root] # 当前层的节点
while curLayer: # 只要当前层有节点就循环
layerValue = [] # 当前层节点对应的值
nextLayer = [] # 下一层节点
for node in curLayer: # 循环当前节点
layerValue.append(node.value) # 添加当前层节点的值
if node.left:
nextLayer.append(node.left) # 添加下一层节点左节点
if node.right:
nextLayer.append(node.right) # 添加下一层节点右节点
print(layerValue) # 打印当前层的值
curLayer = nextLayer # 移动到下一层
if __name__ == '__main__':
root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
layer(root)
'''
['D']
['B', 'E']
['A', 'C', 'G']
['F']
'''
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
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
# 1.5.3 golang
package main
import (
"fmt"
)
type TreeNode struct {
Val int
Left *TreeNode // 左子树
Right *TreeNode // 右子树
}
func levelOrderBottom(root *TreeNode) [][]int {
if root == nil {
return nil
}
vals := [][]int{}
curLayer := []*TreeNode{root} // 当前层的节点
for len(curLayer) > 0 { // 只要当前层有节点就循环
layerValue := []int{} // 当前层节点对应的值
nextLayer := []*TreeNode{} // 下一层节点
for _, node := range curLayer { // 循环当前节点
layerValue = append(layerValue, node.Val) // 添加当前层节点的值
if node.Left != nil {
nextLayer = append(nextLayer, node.Left) // 添加下一层节点左节点
}
if node.Right != nil {
nextLayer = append(nextLayer, node.Right) // 添加下一层节点右节点
}
}
curLayer = nextLayer // 移动到下一层
vals = append([][]int{layerValue}, vals...) // 将当前层追加到列表头部
}
return vals
}
func main() {
root := TreeNode{
Val: 3,
Left: &TreeNode{
Val: 9,
},
Right: &TreeNode{
Val: 20,
Left: &TreeNode{
Val: 15,
},
Right: &TreeNode{
Val: 7,
},
},
}
vals := levelOrderBottom(&root)
fmt.Println(vals) // [[15,7],[9,20],[3]]
}
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
44
45
46
47
48
49
50
51
52
53
54
55
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
44
45
46
47
48
49
50
51
52
53
54
55
# 02.广度优先
- D B E A C G F
# 2.1 栈实现BFS
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left # 左子树
self.right = right # 右子树
# 广度优先搜索
def bfs(root):
res = []
q = [root] # 先把根节点放进队列中
while q: # 当队列不为空时进入循环体
current_node = q.pop(0) # 取出队列的第一个节点
print(current_node.value)
if current_node.left: # 如果左子树不为空,就加入队列
q.append(current_node.left)
if current_node.right: # 如果右子树不为空,就加入队列
q.append(current_node.right)
return res
if __name__ == '__main__':
root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
bfs(root) # D B E A C G F
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 2.2 分层思想
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left # 左子树
self.right = right # 右子树
def bfs(root):
curLayer = [root] # 当前层的节点
while curLayer: # 只要当前层有节点就循环
nextLayer = [] # 下一层节点
for node in curLayer: # 循环当前节点
print(node.value)
if node.left:
nextLayer.append(node.left) # 添加下一层节点左节点
if node.right:
nextLayer.append(node.right) # 添加下一层节点右节点
curLayer = nextLayer # 移动到下一层
if __name__ == '__main__':
root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
bfs(root) # D B E A C G F
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 03.深度优先
- D B A C E G F
# 3.1 栈实现DFS
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left # 左子树
self.right = right # 右子树
# 深度优先搜索
def dfs(root):
res = []
q = [root] # 先把根节点放进栈中
while q: # 当栈不为空时进入循环体
current_node = q.pop() # 取出栈顶节点
print(current_node.value)
if current_node.right: # 如果右子树不为空,就压入栈
q.append(current_node.right)
if current_node.left: # 如果左子树不为空,就压入栈
q.append(current_node.left)
return res
if __name__ == '__main__':
root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
dfs(root) # D B A C E G F
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 3.2 递归实现DFS
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left # 左子树
self.right = right # 右子树
# 深度优先搜索
# 使用递归实现深度优先搜索
def dfs_recur(node):
if not node: # 递归结束的条件是当该节点为None时
return
print(node.value)
dfs_recur(node.left) # 对左子树进行递归
dfs_recur(node.right) # 对右子树进行递归
if __name__ == '__main__':
root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))
dfs_recur(root) # D B A C E G F
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 04.路径总和
# 4.1 题目描述
- 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum
- 判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum
输入:root = [1,2,3], targetSum = 5
输出:false
1
2
2
# 4.2 解题思路
- 假定从根节点到当前节点的值之和为
val
,我们可以将这个大问题转化为一个小问题 - 是否存在从当前节点的子节点到叶子的路径,满足其路径和为
sum - val
。 - 若当前节点就是叶子节点,那么我们直接判断
sum
是否等于val
即可 - 若当前节点不是叶子节点,我们只需要递归地询问它的子节点是否能满足条件即可。
class ListNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left # 左子树
self.right = right # 右子树
def hasPathSum(root, sum):
if not root:
return False
if not root.left and not root.right:
return sum == root.val
return hasPathSum(root.left, sum - int(root.val)) or hasPathSum(root.right, sum - int(root.val))
if __name__ == '__main__':
root = ListNode(1, ListNode(2), ListNode(3))
ret = hasPathSum(root, 3)
print(ret) # True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 05.二叉树直径
# 5.1 题目描述
- 给定一棵二叉树,你需要计算它的直径长度。
- 一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
- 这条路径可能穿过也可能不穿过根结点。
1
/ \
2 3
/ \
4 5
1
2
3
4
5
2
3
4
5
- 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]
# 5.2 解题思路
- 假设我们知道对于该节点的左儿子向下遍历经过最多的节点数 L(即以左儿子为根的子树的深度)
- 和其右儿子向下遍历经过最多的节点数 R(即以右儿子为根的子树的深度
- 那么以该节点为起点的路径经过节点数的最大值即为 L+R+1
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def longestTree(self, root):
self.ans = 1
def depth(node):
if not node: return 0 # 访问到空节点了,返回0
L = depth(node.left) # 左儿子为根的子树的深度
R = depth(node.right) # 右儿子为根的子树的深度
self.ans = max(self.ans, L + R + 1) # 计算d_node即L+R+1 并更新ans
return max(L, R) + 1 # 返回该节点为根的子树的深度
depth(root)
return self.ans - 1
if __name__ == '__main__':
root = TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)), TreeNode(3))
print( Solution().longestTree(root) ) # 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 06.对称二叉树
# 6.1 题目描述
- 给定一个二叉树,检查它是否是镜像对称的。
- 例如,二叉树
[1,2,2,3,4,4,3]
是对称的
1
/ \
2 2
/ \ / \
3 4 4 3
1
2
3
4
5
2
3
4
5
# 6.2 解题思路
- 从树的根节点进行递归
- 递归结束有三种情况
- 第一:递归到两个节点都为空,证明前面的所有结果都是符合的,返回True
- 第二:递归过程中,有对称的两个节点值不相同,返回False
- 得三:递归到最后,两个节点中有一个为空,那么也返回False
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isDC(root):
def dfs(left,right):
if not left and not right: # 递归的终止条件是两个节点都为空
return True
if not (left and right): # 或者两个节点中有一个为空
return False
if left.val!=right.val: # 或者两个节点的值不相等
return False
# dfs() and dfs():的意思是只有and前面的dfs函数返回True才会执行后面dfs函数
# dfs() or dfs(): 的意思是无论and前面的dfs执行结果是什么,都会执行后面的dfs
return dfs(left.left,right.right) and dfs(left.right,right.left)
return dfs(root.left,root.right) # 用递归函数,比较左节点,右节点
if __name__ == '__main__':
root = TreeNode(
1,
left=TreeNode(2,TreeNode(3),TreeNode(4)),
right=TreeNode(2,TreeNode(4),TreeNode(3)),
)
print(isDC(root)) # True
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
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
# 07.二叉树最大深度
# 7.1 题目描述
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
下面这颗树最大深度为3
3
/ \
9 20
/ \
15 7
/
10
1
2
3
4
5
6
7
2
3
4
5
6
7
# 7.2 解题思路
- 深度优先搜索
- 如果我们知道了左子树和右子树的最大深度 l 和 r,那么该二叉树的最大深度即为
max(l,r) + 1
- 而左子树和右子树的最大深度又可以以同样的方式进行计算
- 在计算当前二叉树的最大深度时,可以先递归计算出其左子树和右子树的最大深度
- 然后在 O(1) 时间内计算出当前二叉树的最大深度。
- 递归在访问到空节点时退出。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if root is None: return 0
l = maxDepth(root.left)
r = maxDepth(root.right)
return max(l, r) + 1
if __name__ == '__main__':
root = TreeNode(3,
left=TreeNode(9),
right=TreeNode(20, TreeNode(15), TreeNode(7, TreeNode(10)))
)
print(maxDepth(root)) # 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 08.有序数组转搜索树
# 8.1 题目描述
给你一个整数数组
nums
,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:
1
2
3
2
3
# 8.2 解题思路
- 二叉搜索树的中序遍历是升序序列,因此可以确保数组是二叉搜索树的中序遍历序列。
- 选择中间位置左边的数字作为根节点
- 则
根节点的下标为mid=(left+right)/2
,此处的除法为整数除法。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def trees(nums):
def helper(left, right):
if left > right:
return None
# 总是选择中间位置左边的数字作为根节点
mid = (left + right) // 2
root = TreeNode(nums[mid])
root.left = helper(left, mid - 1)
root.right = helper(mid + 1, right)
return root
return helper(0, len(nums) - 1)
print( trees([-10,-3,0,5,9]) )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 09.平衡二叉树
# 9.1 题目描述
# 平衡二叉树 (opens new window)
给定一个二叉树,判断它是否是高度平衡的二叉树。
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
# 9.2 自顶向下的递归
- 对于当前遍历到的节点,首先计算左右子树的高度
- 如果左右子树的高度差是否不超过 1,再分别递归地遍历左右子节点
- 并判断左子树和右子树是否平衡。
- 这是一个自顶向下的递归的过程。
class Solution:
def isBalanced(self, root):
def height(root):
if not root: return 0
return max(height(root.left), height(root.right)) + 1
if not root: return True
return abs(height(root.left) - height(root.right)) <= 1 \
and self.isBalanced(root.left) and self.isBalanced(root.right)
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 10.移动零
# 10.1 题目描述
- 移动零 (opens new window)
- 给定一个数组
nums
,编写一个函数将所有0
移动到数组的末尾,同时保持非零元素的相对顺序。
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
1
2
2
# 10.2 解题思路
- 我们创建两个指针i和j,第一次遍历的时候
指针j用来记录当前有多少 "非0元素"
。 - 即遍历的时候每遇到一个非0元素就将其往数组左边挪
- 第一次遍历完后,j指针的下标就指向了最后一个非0元素下标。
- 第二次遍历的时候,起始位置就从j开始到结束,将剩下的这段区域内的元素全部置为0。
def moveZeroes(nums):
j = 0 # j指针记录非0的个数,只要是非0的统统都赋给nums[j]
for i in range(len(nums)):
if nums[i]:
nums[j] = nums[i]
j += 1
# 非0元素统计完了,剩下的都是0了,所以第二次遍历把末尾的元素都赋为0即可
for i in range(j,len(nums)):
nums[i] = 0
return nums
print( moveZeroes([0,1,0,3,12]) ) # [1, 3, 12, 0, 0]
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 11.二叉树的最小深度
# 11.1 题目描述
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
**说明:**叶子节点是指没有子节点的节点。
输入:root = [3,9,20,null,null,15,7]
输出:2
1
2
2
# 11.2 深度优先搜索
首先可以想到使用深度优先搜索的方法,遍历整棵树,记录最小深度。
对于每一个非叶子节点,我们只需要分别计算其左右子树的最小叶子节点深度。
这样就将一个大问题转化为了小问题,可以递归地解决该问题。
def minDepth(root):
if not root:
return 0
if not root.left and not root.right:
return 1
# 因为本题使用递归方法实现,所以初始值设置为 10**10=10000000000作为初始化深度没问题
min_depth = 10 ** 10
if root.left:
min_depth = min(minDepth(root.left), min_depth)
if root.right:
min_depth = min(minDepth(root.right), min_depth)
return min_depth + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 12.二叉树的右视图
# 12.1 题目说明
给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 12.2 广度优先思路
- 我们可以对二叉树进行层次遍历,那么对于每层来说,最右边的结点一定是最后被遍历到的。
- 二叉树的层次遍历可以用广度优先搜索实现。
#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left # 左子树
self.right = right # 右子树
def layer(root):
ret = []
curLayer = [root] # 当前层的节点
while curLayer: # 只要当前层有节点就循环
layerValue = [] # 当前层节点对应的值
nextLayer = [] # 下一层节点
for node in curLayer: # 循环当前节点
layerValue.append(node.val) # 添加当前层节点的值
if node.left:
nextLayer.append(node.left) # 添加下一层节点左节点
if node.right:
nextLayer.append(node.right) # 添加下一层节点右节点
ret.append(layerValue[-1])
curLayer = nextLayer # 移动到下一层
return ret
if __name__ == '__main__':
root = Node(1, left=Node(2,right=Node(5)), right=Node(3, left=Node(4)))
print( layer(root) ) # [1, 3, 4]
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
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
编辑 (opens new window)
上次更新: 2024/3/13 15:35:10