先序遍历
时间: 2023-06-22 21:05:13 浏览: 55
先序遍历是二叉树遍历的一种方法,遍历顺序是先遍历根节点,然后遍历左子树,最后遍历右子树。具体实现可以采用递归或栈的方式。
以下是递归实现的先序遍历代码:
```
void preOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
// 遍历根节点
cout << root->val << " ";
// 遍历左子树
preOrder(root->left);
// 遍历右子树
preOrder(root->right);
}
```
以下是栈实现的先序遍历代码:
```
void preOrder(TreeNode* root) {
stack<TreeNode*> st;
if (root) {
st.push(root);
}
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
// 遍历根节点
cout << node->val << " ";
// 先将右子树入栈,再将左子树入栈,保证左子树先被访问
if (node->right) {
st.push(node->right);
}
if (node->left) {
st.push(node->left);
}
}
}
```