二叉树基础#

二叉树是每个节点最多有两个子节点的树结构，常用于表示层次关系。
二叉树的基本操作包括插入、删除、查找等。
二叉树的遍历方式有前序、中序、后序和层序遍历。

递归遍历#

递归是处理树结构的常用方法，通过递归函数访问每个节点。
前序遍历：访问根节点 -> 访问左子树 -> 访问右子树。
中序遍历：访问左子树 -> 访问根节点 -> 访问右子树。
后序遍历：访问左子树 -> 访问右子树 -> 访问根节点。

144. 二叉树的前序遍历#

LeetCode 144. 二叉树的前序遍历

1
from typing import Optional, List
2

3
# Definition for a binary tree node.
4
class TreeNode:
5
    def __init__(self, val=0, left=None, right=None):
6
        self.val = val
7
        self.left = left
8
        self.right = right
9

10
class Solution:
11
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
12
        res = []
13
        self.dfs(root, res)
14
        return res
15

16
    def dfs(self, root, res):
17
        if not root:
18
            return
19
        # 先访问根节点
20
        res.append(root.val)
21
        # 再访问左子树
22
        self.dfs(root.left, res)
23
        # 最后访问右子树
24
        self.dfs(root.right, res)

94. 二叉树的中序遍历#

LeetCode 94. 二叉树的中序遍历

1
class Solution:
2
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
3
        res = []
4
        self.dfs(root, res)
5
        return res
6

7
    def dfs(self, root, res):
8
        if not root:
9
            return
10
        # 先访问左子树
11
        self.dfs(root.left, res)
12
        # 访问根节点
13
        res.append(root.val)
14
        # 再访问右子树
15
        self.dfs(root.right, res)

145. 二叉树的后序遍历#

LeetCode 145. 二叉树的后序遍历

1
class Solution:
2
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
3
        res = []
4
        self.dfs(root, res)
5
        return res
6

7
    def dfs(self, root, res):
8
        if not root:
9
            return
10
        # 先访问左子树
11
        self.dfs(root.left, res)
12
        # 再访问右子树
13
        self.dfs(root.right, res)
14
        # 最后访问根节点
15
        res.append(root.val)

层序遍历#

层序遍历是按层次从上到下、从左到右访问二叉树的节点。
通常使用队列（Queue）来实现层序遍历。

通用模板#

1
from collections import deque
2
from typing import Optional, List
3

4
def level_order_traversal(root: Optional[TreeNode]) -> List[List[int]]:
5
    res = []
6
    if not root:
7
        return res
8
    q = deque([root])  # 初始化队列，放入根节点
9
    while q:
10
        size = len(q)
11
        level = []
12
        for _ in range(size):
13
            cur = q.popleft()  # 当前层出队
14
            level.append(cur.val)
15
            if cur.left:
16
                q.append(cur.left)  # 左子节点入队
17
            if cur.right:
18
                q.append(cur.right)  # 右子节点入队
19
        res.append(level)  # 当前层结束，添加到结果中
20
    return res