二叉树练习

描述
给你二叉树的根节点 root ，返回它节点值的 前、中、后序遍历。
数据范围：二叉树的节点数量满足 0≤n≤100 ，二叉树节点的值满足1≤val≤100 ，树的各节点的值各不相同

BM23 二叉树的前序遍历

示例1
输入：{
   1,#,2,3}
返回值：[1,2,3]

1
2
3
4
5

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    def preorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        tree_list = []
        self.perorder(tree_list, root)
        return tree_list
    
    def perorder(self, tree_list: List[int], root: TreeNode):
        if root is None:
            return 
        tree_list.append(root.val)
        self.perorder(tree_list, root.left)
        self.perorder(tree_list, root.right)
            
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

BM24 二叉树的中序遍历

示例1
输入：{
   1,2,#,#,3}
返回值：[2,3,1]
  
示例2
输入：{
   }
返回值：[]

示例3
输入：{
   1,2}
返回值：[2,1]
 
示例4
输入：{
   1,#,2}
返回值：[1,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
import sys
sys.setrecursionlimit(10000)
class Solution:
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        tree_list = []
        self.inorder(root, tree_list)
        return tree_list
    
    def inorder(self, root: TreeNode, tree_list:List[int]):
        if root is None:
            return
        
        self.inorder(root.left, tree_list)
        tree_list.append(root.val)
        self.inorder(root.right, tree_list)
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

BM25 二叉树的后序遍历

示例1
输入：{
   1,#,2,3}
返回值：[3,2,1]
  
示例2
输入：{
   1}
返回值：[1]
1
2
3
4
5
6
7
8
9

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        tree_list = []
        self.postorder(tree_list, root)
        return tree_list
    
    def postorder(self, tree_list:List[int], root: TreeNode):
        if root is None:
            return
        
        self.postorder(tree_list, root.left)
        self.postorder(tree_list, root.right)
        tree_list.append(root.val)
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

BM26 求二叉树的层序遍历

描述
给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
]
数据范围：二叉树的节点数满足 1≤n≤10^5

示例1
输入：{
   1,2}
返回值：[[1],[2]]

示例2
输入：{
   
1
2
3
4
5
6
7