0144. 二叉树的前序遍历【简单】
1. 📝 题目描述
给你二叉树的根节点 root,返回它节点值的前序遍历。
示例 1:

txt
输入:root = [1,null,2,3]
输出:[1,2,3]1
2
2
示例 2:
txt
输入:root = []
输出:[]1
2
2
示例 3:
txt
输入:root = [1]
输出:[1]1
2
2
示例 4:

txt
输入:root = [1,2]
输出:[1,2]1
2
2
示例 5:

txt
输入:root = [1,null,2]
输出:[1,2]1
2
2
提示:
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶:递归算法很简单,你可以通过迭代算法完成吗?
2. 🎯 s.1 - 递归
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function (root) {
const result = []
const traverse = (node) => {
if (!node) return
// 前序遍历:根 -> 左 -> 右
result.push(node.val)
traverse(node.left)
traverse(node.right)
}
traverse(root)
return result
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
- 时间复杂度:
,其中 n 是二叉树的节点数,需要遍历所有节点 - 空间复杂度:
,递归调用栈的深度最多为 n(最坏情况下树退化为链表)
算法思路:
- 前序遍历顺序:根节点 -> 左子树 -> 右子树
- 递归处理:先访问根节点,再遍历左子树,最后遍历右子树
- 将访问的节点值依次存入结果数组
3. 🎯 s.2 - 迭代
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function (root) {
if (root === null) return []
const result = []
const stack = [root]
while (stack.length > 0) {
// 弹出栈顶节点并访问
const node = stack.pop()
result.push(node.val)
// 先压入右子节点,再压入左子节点(保证左子树先遍历)
if (node.right !== null) stack.push(node.right)
if (node.left !== null) stack.push(node.left)
}
return result
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
- 时间复杂度:
,其中 n 是二叉树的节点数,需要遍历所有节点 - 空间复杂度:
,栈的最大深度为 n
算法思路:
- 使用栈存储节点,每次弹出节点时立即访问
- 先压入右子节点,再压入左子节点(保证左子树先被弹出)
- 这样可以保证根-左-右的遍历顺序