二叉树的前序遍历 图解题解
这道题到底在问什么
- 输入
- root=[1,null,2,3]
- 输出
- [1,2,3]
- 输入
- root=[1,2,3,4,5]
- 输出
- [1,2,4,5,3]
最优解：一步一步想明白
- 3记住「先记根,再左,再右」,递归栈负责回溯。下面逐帧走一遍这棵树。
- 4整棵树先看清这棵树:根是 50,它的左孩子 30(下面挂着 20、40)、右孩子 80(下面挂着 70)。前序遍历从根 50 出发,一路「先根后左再右」地往下走。
- 5进入 值50递归进入节点 值50(紫色)。前序的规矩是「根在最前」,所以一进来先轮到 值50 自己。
- 6记下 值50把 值50 记进结果(它变绿),现在结果是 [50]。根记完了,接着先钻它的左子树。
- 7进入 值30递归进入节点 值30(紫色)。前序的规矩是「根在最前」,所以一进来先轮到 值30 自己。
- 8记下 值30把 值30 记进结果(它变绿),现在结果是 [50, 30]。根记完了,接着先钻它的左子树。
- 9进入 值20递归进入节点 值20(紫色)。前序的规矩是「根在最前」,所以一进来先轮到 值20 自己。
- 10记下 值20把 值20 记进结果(它变绿),现在结果是 [50, 30, 20]。根记完了,接着先钻它的左子树。
- 11值20 子树完值20 这棵子树全部遍历完毕,从递归里返回到上一层 值30。
- 12回到 值30值30 的左子树整段都走完了,递归回到 值30。前序里左边处理完,接下来轮到它的右子树。
- 13进入 值40递归进入节点 值40(紫色)。前序的规矩是「根在最前」,所以一进来先轮到 值40 自己。
- 14记下 值40把 值40 记进结果(它变绿),现在结果是 [50, 30, 20, 40]。根记完了,接着先钻它的左子树。
- 15值40 子树完值40 这棵子树全部遍历完毕,从递归里返回到上一层 值30。
- 16值30 子树完值30 这棵子树全部遍历完毕,从递归里返回到上一层 值50。
- 17回到 值50值50 的左子树整段都走完了,递归回到 值50。前序里左边处理完,接下来轮到它的右子树。
- 18进入 值80递归进入节点 值80(紫色)。前序的规矩是「根在最前」,所以一进来先轮到 值80 自己。
- 19记下 值80把 值80 记进结果(它变绿),现在结果是 [50, 30, 20, 40, 80]。根记完了,接着先钻它的左子树。
- 20进入 值70递归进入节点 值70(紫色)。前序的规矩是「根在最前」,所以一进来先轮到 值70 自己。
- 21记下 值70把 值70 记进结果(它变绿),现在结果是 [50, 30, 20, 40, 80, 70]。根记完了,接着先钻它的左子树。
- 22值70 子树完值70 这棵子树全部遍历完毕,从递归里返回到上一层 值80。
- 23值80 右空值80 没有右孩子,右子树为空。到这儿,值80 的左、右子树都处理完了。
- 24值80 子树完值80 这棵子树全部遍历完毕,从递归里返回到上一层 值50。
- 25值50 子树完值50 是根,它的整棵树都遍历完了,递归回到最外层,前序遍历到此结束。
- 26遍历完成整棵树前序遍历完成,结果是 50、30、20、40、80、70。回头看:每到一个节点都「先记自己、再左、再右」,递归栈帮我们记住回溯路径,每个节点恰好访问一次,所以是 O(n)。
⚠️ 容易写错的地方
✗ 错：把顺序写成 左→根→右 或 左→右→根
✓ 对：前序必须 根 → 左 → 右,记根的语句放在两个递归调用之前
记录语句的位置就决定了前/中/后序,放错位置遍历顺序就全变了
✗ 错：忘了空节点的递归出口
✓ 对：进入 dfs 先判 node 为空就 return
不判空会对空指针取 left/right,直接崩溃或越界
✗ 错：迭代写法压栈顺序反了
✓ 对：用显式栈时先压右孩子、再压左孩子
栈后进先出,先压右后压左,才能保证左孩子先被弹出、先被处理,符合前序
完整代码（Python / C++ / Java）
Python
from typing import List, Optional
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]:
ans = []
def dfs(node):
if node:
ans.append(node.val); dfs(node.left); dfs(node.right)
dfs(root)
return ansC++
#include <algorithm>
#include <climits>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution { public: vector<int> preorderTraversal(TreeNode* root){ vector<int> ans; function<void(TreeNode*)> dfs=[&](TreeNode* n){ if(!n) return; ans.push_back(n->val); dfs(n->left); dfs(n->right); }; dfs(root); return ans; } };Java
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}
class Solution { public List<Integer> preorderTraversal(TreeNode root){ ArrayList<Integer> ans=new ArrayList<>(); dfs(root,ans); return ans; } void dfs(TreeNode n,List<Integer> ans){ if(n==null)return; ans.add(n.val); dfs(n.left,ans); dfs(n.right,ans); } }复杂度
时间
O(n)
每个节点恰好被访问、被记录一次,n 是节点总数
空间
O(h)
递归调用栈的深度等于树高 h;平衡树约 O(log n),退化成链时最坏 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二叉树的前序遍历 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
不用递归怎么做前序?+
用一个显式栈:先把根压栈;每次弹出栈顶节点、记录它的值,然后先压它的右孩子、再压它的左孩子(为空就不压);循环到栈空。先压右后压左,保证左孩子先被弹出处理,效果和递归前序一致,空间同样是 O(h)。
前序、中序、后序在代码上差别在哪?+
差别只有「记录根的那行语句」放在哪:放在两个递归调用之前是前序(根左右)、放在中间是中序(左根右)、放在之后是后序(左右根)。遍历框架完全一样,挪一行就切换。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 二叉树的前序遍历 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。