二叉树的深度优先遍历

🟢 Easy · 🏷️ 树、递归、DFS · LeetCode#94（这篇同时覆盖 #144 前序、#145 后序）

📖 题目

给二叉树根节点，分别返回前序、中序、后序遍历的结果。

遍历	顺序	记忆
前序 Preorder	根→左→右	Pre=前，根在前
中序 Inorder	左→根→右	In=中，根在中
后序 Postorder	左→右→根	Post=后，根在后

💡 思路

三种遍历唯一的区别是根节点的访问时机——递归结构完全一样，只是把 [root.val] 插在拼接的不同位置。

以根 1、左子 2、右子 3 为例：前序 [1,2,3]（根先出现）、中序 [2,1,3]（根在中间）、后序 [2,3,1]（根最后出现）。

💻 代码

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

三者复杂度相同：时间 O(n)，空间 O(n)（递归栈 + 结果列表）。

实际场景里，中序遍历对二叉搜索树（BST）能直接得到有序序列，是比较常考的点；前序像"先处理自己再处理孩子"，适合复制一棵树；后序像"先处理孩子再处理自己"，适合删除一棵树。