1 分治法-递归
代码语言：javascript
复制/**
* 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:
void dfs(TreeNode* root, vector<int>& vec) {
if (!root) return;
vec.push_back(root->val);
dfs(root->left, vec);
dfs(root->right, vec);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vec;
dfs(root, vec);
return vec;
}
};
2 迭代法-栈
代码语言：javascript
复制class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if (!root) return {};
vector<int> vec;
stack<TreeNode*> stk;
auto node = root;
while (!stk.empty() || node) {
// 1.遍历到最左子节点
while (node) {
vec.emplace_back(node->val);
stk.emplace(node);
node = node->left;
}
// 2.遍历最左子节点的右子树
node = stk.top(); stk.pop();
node = node->right;
}
return vec;
}
};
