- 前序遍历： 节点-左子树-右子树（中-左-右）
- 中序遍历： 左子树-节点-右子树（左-中-右）
- 后续遍历： 左子树-右子树-节点（左-右-中）
数据结构
// 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) {
}
};
递归版本
前序遍历
void preorder(treenode * root){
cout<val; // process node
preorder(root->left);
preorder(root->right);
}
中序遍历
void inorder(treenode * root){
inorder(root->left);
cout<val; // process node
inorder(root->right);
}
后序遍历
void postorder(treenode * root){
postorder(root->left);
postorder(root->right);
cout<val; // process node
}
迭代版本
前序遍历
vector preordertraversal(treenode * root){
vector res;
if(root == null) return res;
stacks;
s.push(root);
while(!s.empty()){
treenode * temp = s.top();
s.pop();
res.push_back(temp->val);
if(node->right) s.push(node->right);
if(ndoe->left) s.push(node->left);
}
return res;
}
中序遍历
vector inordertraversal(treenode * root){
vector res;
if(root == null) return res;
stacks;
treenode * cur = root;
while(!cur||!s.empty()){
if(cur != null){
s.push(cur);
cur = cur->left;
}else{
cur = s.top();
s.pop();
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
后序遍历：
前序（中左右）- 调整（中右左）-翻转（左右中）-得到后续遍历
vector postordertraversal(treenode* root){
vector res;
if(root == null) return res;
stack s;
s.push(root);
while(!s.empty()){
treenode * temp = s.top();
s.pop();
res.push_back(temp->val);
if(temp->left) s.push(temp->left);
if(temp->right) s.push(temp->right);
}
res.reverse(res.begin(), res.end());
}
- 参考文献
彻底吃透二叉树的前中后序递归法和迭代法！！