LeetCode 题解工作台
二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。 示例 1： 输入： root = [1,null,2,3] 输出： [1,2,3] 解释： 示例 2： 输入： root = [1,2,3,4,5,null,8,null,null,6,7,9] 输出： [1,2,4,5,6,7,3,8,…
4
题型
6
代码语言
3
相关题
当前训练重点
简单 · 二分·树·traversal
答案摘要
我们先访问根节点，然后递归左子树和右子树。 时间复杂度 ，空间复杂度 。其中 是二叉树的节点数，空间复杂度主要取决于递归调用的栈空间。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
解题思路
方法一：递归遍历
我们先访问根节点，然后递归左子树和右子树。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点数，空间复杂度主要取决于递归调用的栈空间。
# 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]:
def dfs(root):
if root is None:
return
ans.append(root.val)
dfs(root.left)
dfs(root.right)
ans = []
dfs(root)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each node is visited once. Space complexity is O(h) for recursion or O(n) for the stack in the worst case, where n is the number of nodes and h is the tree height. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looking for correct preorder sequence adherence and null handling.
- question_mark
Checking if candidate differentiates between recursion and iterative stack approaches.
- question_mark
Assessing ability to track traversal state without missing leaf nodes.
常见陷阱
外企场景- error
Pushing left child after right child incorrectly, reversing preorder order.
- error
Forgetting to check for null nodes, causing runtime errors.
- error
Assuming all trees are complete and not handling sparse trees properly.
进阶变体
外企场景- arrow_right_alt
Inorder and postorder traversal with similar state-tracking logic.
- arrow_right_alt
Binary tree with additional constraints, such as skipping certain values.
- arrow_right_alt
Traversals returning node objects instead of values for processing.