二叉树遍历
二叉树安按照访问元素的顺序不同，分为前中后序、已经层序遍历，其中前中后续遍历又称为深度优先遍历(DFS具体有递归和迭代两种写法)，层序遍历又称为广度优先遍历（BFS）
# 前中后序遍历
# 1.1. 二叉树的前序遍历 (opens new window)
示例 1：
输入：root = [1,null,2,3] 输出：[1,2,3]1
2示例 2：
输入：root = [] 输出：[]1
2示例 3：
输入：root = [1] 输出：[1]1
2示例 4：
输入：root = [1,2] 输出：[1,2]1
2示例 5：
输入：root = [1,null,2] 输出：[1,2]1
2提示：
- 树中节点数目在范围
[0, 100]内-100 <= Node.val <= 100**进阶：**递归算法很简单，你可以通过迭代算法完成吗？
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ret, stack = [], []
while root or stack:
while root:
ret.append(root.val)
stack.append(root)
root = root.left
cur = stack.pop()
root = cur.right
return ret
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
func preorderTraversal(root *TreeNode) []int {
ret, stack := make([]int, 0), make([] *TreeNode, 0)
for root !=nil || len(stack)>0{
for root !=nil {
ret = append(ret, root.Val)
stack = append(stack, root)
root = root.Left
}
cur := stack[len(stack)-1]
stack = stack[:len(stack)-1]
root = cur.Right
}
return ret
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
// Make sure to add code blocks to your code group
# 1.2. 二叉树的中序遍历 (opens new window)
给定一个二叉树的根节点
root，返回 它的 中序 遍历 。示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]1
2示例 2：
输入：root = [] 输出：[]1
2示例 3：
输入：root = [1] 输出：[1]1
2提示：
- 树中节点数目在范围
[0, 100]内-100 <= Node.val <= 100进阶: 递归算法很简单，你可以通过迭代算法完成吗？
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
"""
中序遍历：左-->中-->右
如果有左子树，将左子树入栈，同时将root的指针移动到左子树
"""
ret, stack = [], []
while root or stack:
while root:
stack.append(root)
root = root.left
cur = stack.pop()
ret.append(cur.val)
root = cur.right
return ret
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
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
ret, stack := make([]int, 0), make([]*TreeNode, 0)
for root !=nil || len(stack)>0{
for root != nil{
stack = append(stack, root)
root = root.Left
}
cur := stack[len(stack)-1]
stack = stack[:len(stack)-1]
ret = append(ret, cur.Val)
root = cur.Right
}
return ret
}
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
// Make sure to add code blocks to your code group
# 1.3. 二叉树的后序遍历 (opens new window)
给你一棵二叉树的根节点
root，返回其节点值的 后序遍历 。示例 1：
输入：root = [1,null,2,3] 输出：[3,2,1]1
2示例 2：
输入：root = [] 输出：[]1
2示例 3：
输入：root = [1] 输出：[1]1
2提示：
- 树中节点的数目在范围
[0, 100]内-100 <= Node.val <= 100**进阶：**递归算法很简单，你可以通过迭代算法完成吗？
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ret, stack = [], []
while root or stack:
while root:
ret.append(root.val)
stack.append(root)
root = root.right
cur = stack[len(stack)-1]
root = cur.left
stack = stack[:len(stack)-1]
return ret[::-1]
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
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func postorderTraversal(root *TreeNode) []int {
ret, stack := make([]int, 0), make([]*TreeNode, 0)
for root !=nil || len(stack) >0{
for root !=nil{
ret = append(ret, root.Val)
stack = append(stack, root)
root = root.Right
}
cur := stack[len(stack)-1]
stack = stack[:len(stack)-1]
root = cur.Left
}
for i,j:=0, len(ret)-1;i<j;i, j= i+1, j -1{
ret[i], ret[j] = ret[j], ret[i]
}
return ret
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Make sure to add code blocks to your code group
# 1.3. 二叉树的层遍历 (opens new window)
给你二叉树的根节点
root，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]1
2示例 2：
输入：root = [1] 输出：[[1]]1
2示例 3：
输入：root = [] 输出：[]1
2
3
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
deque = collections.deque([root])
ret = list()
while deque:
temp = list()
for _ in range(len(deque)):
cur = deque.popleft()
temp.append(cur.val)
if cur.left:
deque.append(cur.left)
if cur.right:
deque.append(cur.right)
ret.append(temp)
return ret
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
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
ret := [][]int{}
if root == nil{
return ret
}
deque := []*TreeNode{root}
for len(deque) >0 {
cur_len := len(deque)
// temp_node := make([]*TreeNode, 0)
tmp := make([]int, 0)
for j:=0;j<cur_len;j++{
node := deque[j]
tmp = append(tmp, node.Val)
if node.Left != nil{
deque = append(deque, node.Left)
}
if node.Right != nil{
deque = append(deque, node.Right)
}
}
ret = append(ret, tmp)
deque = deque[cur_len:]
}
return ret
}
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
// Make sure to add code blocks to your code group
编辑 (opens new window)
上次更新: 2024/12/13 19:48:29