144. 二叉树的前序遍历

Posted on Edited on In Views: Word count in article: 391 Reading time ≈ 1 mins.

144. 二叉树的前序遍历

题目链接：144. 二叉树的前序遍历

题目描述

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

核心思考：深度优先搜索 (DFS)

二叉树的前序遍历遵循 “根 -> 左 -> 右” 的顺序。这是一种典型的深度优先搜索。

  1. 递归逻辑：当访问到一个节点时，首先将其值记录到结果列表中，然后递归地处理其左子树，最后递归地处理其右子树。
  2. 基准情形：如果当前节点为空，则直接返回，不进行任何处理。

虽然前序遍历也可以通过迭代（模拟栈）来高效实现，但递归写法因其简洁直观的特点，仍然是理解树遍历的基础。

解题思路 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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]:
        res = []
        
        def dfs(node):
            if not node:
                return
            # 前序：根 -> 左 -> 右
            res.append(node.val)
            dfs(node.left)
            dfs(node.right)
            
        dfs(root)
        return res

复杂度分析

  • 时间复杂度：$O(N)$，其中 $N$ 是二叉树的节点数。每个节点被访问且处理且仅处理一次。
  • 空间复杂度：$O(H)$，其中 $H$ 是树的高度。主要由递归调用的栈空间产生。平均情况下高度平衡的树为 $O(\log N)$，最坏情况（退化为链）下为 $O(N)$。