二叉树的递归遍历

二叉树的递归遍历，或者说“所有的递归”都离不开三个因素

确定递归函数的input与output(参数与返回值)
终止条件
单层递归的逻辑

以中序遍历为例

确定递归函数的参数与返回值：
1. 需要有“当前节点”，其次，需要将中序遍历的结果放在res数组中;可以不返回
2. def traversal(cur: TreeNode, res: List): ..... return
终止条件
1. 当“当前节点”为空时，则终止
2. if not cur: return

单层递归的逻辑

先将"cur.val"添加到res中，再递归遍历"cur.left"，最终递归遍历"cur.right"

res.append(cur.val)    // 中
traversal(cur.left, res);  // 左
traversal(cur.right, res); // 右
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96





# 144. 二叉树的前序遍历

https://leetcode.cn/problems/binary-tree-preorder-traversal/

给你二叉树的根节点 `root` ，返回它节点值的 **前序** 遍历。

 

**示例 1：**

**输入：**root = [1,null,2,3]

**输出：**[1,2,3]

**解释：**

![img](https://assets.leetcode.com/uploads/2024/08/29/screenshot-2024-08-29-202743.png)

**示例 2：**

**输入：**root = [1,2,3,4,5,null,8,null,null,6,7,9]

**输出：**[1,2,4,5,6,7,3,8,9]

**解释：**

![img](https://assets.leetcode.com/uploads/2024/08/29/tree_2.png)

**示例 3：**

**输入：**root = []

**输出：**[]

**示例 4：**

**输入：**root = [1]

**输出：**[1]

 

**提示：**

- 树中节点数目在范围 `[0, 100]` 内
- `-100 <= Node.val <= 100`

 

**进阶：**递归算法很简单，你可以通过迭代算法完成吗？







## 递归思路

1. 确定递归函数的输入&输出；确定终止条件；确定单层递归的逻辑
2. 前序遍历，先记录cur.val，再分别递归左、右子树





## 递归代码

* 时间复杂度O(N)
* 空间复杂度O(1)

```python
# 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:
    # preorder
    def traversal(self, cur: TreeNode, res: List):
        if not cur:
            return
        res.append(cur.val)
        self.traversal(cur.left, res)
        self.traversal(cur.right, res)

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        self.traversal(root, res)
        return res

145. 二叉树的后序遍历

https://leetcode.cn/problems/binary-tree-postorder-traversal/

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

**输入：**root = [1,null,2,3]

输出：[3,2,1]

解释：

示例 2：

**输入：**root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[4,6,7,5,2,9,8,3,1]

解释：

示例 3：

**输入：**root = []

输出：[]

示例 4：

**输入：**root = [1]

输出：[1]

提示：

树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100

**进阶：**递归算法很简单，你可以通过迭代算法完成吗？

递归代码

时间复杂度O(N)
空间复杂度O(1)

# 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 traversal(self, cur: TreeNode, res: List):
        if not cur:
            return
        self.traversal(cur.left, res) # 左
        self.traversal(cur.right, res) # 右
        res.append(cur.val)

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = list()
        self.traversal(root, res)
        return res

二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

示例 1：

1 2	输入：root = [1,null,2,3] 输出：[1,3,2]

示例 2：

1 2	输入：root = [] 输出：[]

示例 3：

1 2	输入：root = [1] 输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归代码

时间复杂度O(N)
空间复杂度O(1)

# 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 traversal(self, cur: TreeNode, res: List):
        if not cur:
            return
        self.traversal(cur.left, res) # 左
        res.append(cur.val)
        self.traversal(cur.right, res) # 右
        

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = list()
        self.traversal(root, res)
        return res