Given the root of a binary tree, return the preorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,2,3]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [1,2,4,5,6,7,3,8,9]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
题目大意
给定一棵二叉树的根节点 root，返回其节点值的前序遍历结果。前序遍历的顺序是「根节点 → 左子树 → 右子树」，遵循 "根 - 左 - 右" 的递归逻辑。
解题思路
前序遍历的核心是先访问根节点，再遍历左子树，最后遍历右子树。主要有两种实现方式：
1. 递归法
直接按照 "根 - 左 - 右" 的顺序递归遍历：
- 访问当前根节点
- 递归遍历左子树
- 递归遍历右子树
2. 迭代法
使用栈来模拟递归过程：
- 将根节点入栈
- 当栈不为空时，弹出栈顶节点并访问
- 先将右子节点入栈（因为栈是后进先出）
- 再将左子节点入栈
- 重复步骤 2-4 直到栈为空
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| /**
* Definition for a binary tree node.
* 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:
// 方法1：递归实现
vector<int> preorderTraversal1(TreeNode* root) {
vector<int> result;
preorderRecursive(root, result);
return result;
}
// 方法2：迭代实现
vector<int> preorderTraversal2(TreeNode* root) {
vector<int> result;
if (root == nullptr) return result;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
// 弹出栈顶节点并访问
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
// 先右后左入栈，保证左子树先处理
if (node->right != nullptr) {
st.push(node->right);
}
if (node->left != nullptr) {
st.push(node->left);
}
}
return result;
}
// 为了提交方便，这里用方法2作为默认实现
vector<int> preorderTraversal(TreeNode* root) {
return preorderTraversal2(root);
}
private:
// 递归辅助函数
void preorderRecursive(TreeNode* root, vector<int>& result) {
if (root == nullptr) return;
result.push_back(root->val); // 访问根节点
preorderRecursive(root->left, result); // 遍历左子树
preorderRecursive(root->right, result); // 遍历右子树
}
};
|
