遍历二叉树先序中后
遍历二叉树先序、中序、后序
在计算机科学中，遍历二叉树是一个经常要用到的算法，经常需要遍历不同类型的树结构，二叉树遍历算法是其中最为常见和重要的算法之一。二叉树遍历分为先序遍历、中序遍历、后序遍历三种，本文将从多个角度分析这三种树遍历的算法原理和实现。
一、先序遍历
首先来看先序遍历，先序遍历的顺序为根结点-左结点-右结点。也就是说，先访问根节点，然后递归遍历左子树再递归遍历右子树。
对于任意一个节点，先把节点输出，再访问它的左子树，最后访问它的右子树。可以通过递归或栈的方式实现。
递归实现：
```
void preOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << endl;
preOrder(root->left);
preOrder(root->right);
}
```
栈实现：
```
void preOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
stack
s.push(root);
while (!s.empty()) {
TreeNode* curr = s.top();
s.pop();
cout << curr->val << endl;
if (curr->right) {
s.push(curr->right);
}
if (curr->left) {
s.push(curr->left);
}
}
}
```
二、中序遍历
中序遍历的顺序为左结点-根结点-右结点。也就是说，先访问左子树，然后访问根节点，最后访问右子树。
对于任意一个节点，先访问它的左子树，然后输出节点的值，最后访问它的右子树。同样也可以通过递归或栈的方式实现。
递归实现：
```
void inOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
inOrder(root->left);
cout << root->val << endl;
inOrder(root->right);
}
```
栈实现：
```
void inOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
stack
TreeNode* curr = root;
while (!s.empty() || curr) {
while (curr) {
s.push(curr);
curr = curr->left;
}
curr = s.top();
s.pop();
cout << curr->val << endl;
curr = curr->right;
}
}
```
三、后序遍历
后序遍历的顺序为左结点-右结点-根节点。也就是说，先访问左子树，然后访问右子树，最后访问根节点。
对于任意一个节点，先访问它的左子树，再访问它的右子树，最后输出节点的值。同样也可以通过递归或栈的方式实现。
递归实现：
```
void postOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->val << endl;
}
```
栈实现：
```
void postOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
stack
s.push(root);
while (!s.empty()) {
TreeNode* curr = s.top();
s.pop();
res.push(curr);
if (curr->left) {
s.push(curr->left);
}
if (curr->right) {
s.push(curr->right);
}
}
while (!res.empty()) {
TreeNode* curr = res.top();
res.pop();
cout << curr->val << endl;
}
}
```
尽管这三种遍历算法看起来很容易，但还是有些需要注意的问题。其中，先序遍历比较简单和常见，中序遍历和后序遍历稍微有些复杂。
