例题
- 中序遍历94. Binary Tree Inorder Traversal
- 先序遍历144. Binary Tree Preorder Traversal
- 后序遍历145. Binary Tree Postorder Traversal
递归栈
递归函数栈的方法很基础，写法也很简单，三种遍历方式之间只需要改变一行代码的位置即可
中序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void inorder(TreeNode* root, vector<int>& v){
if(root != nullptr) {
inorder(root->left, v);
v.push_back(root->val); // 改变位置的代码
inorder(root->right, v);
}
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
inorder(root, v);
return v;
}
};
先序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void inorder(TreeNode* root, vector<int>& v){
if(root != nullptr) {
v.push_back(root->val);
inorder(root->left, v);
inorder(root->right, v);
}
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
inorder(root, v);
return v;
}
};
后序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void inorder(TreeNode* root, vector<int>& v){
if(root != nullptr) {
inorder(root->left, v);
inorder(root->right, v);
v.push_back(root->val);
}
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
inorder(root, v);
return v;
}
};
非递归栈
当树的深度过大时，函数栈可能会溢出，这时候需要我们使用数据结构中的栈，来模拟节点在栈中的压入和弹出
中序遍历
cur指针时刻指向需要处理的节点
如果当前节点不为空，则压入栈中，并改变cur指针指向其左节点
如果当前节点为空，也代表空节点的中序遍历自动完成，无需压栈，这时候需要弹出栈顶的节点，保存栈顶节点的值，并更改cur指向其右子树，以完成右子树的中序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
stack<TreeNode*> s;
TreeNode* cur = root;
while(cur || !s.empty()){
if(cur){
s.push(cur);
cur = cur->left;
} else {
cur = s.top();
s.pop();
v.push_back(cur->val);
cur = cur->right;
}
}
return v;
}
};
先序遍历
先序遍历与中序遍历代码相比只改变了保存节点的值的代码的位置，当先访问根的时候就记录节点，而不是等左子树遍历完，弹出根节点的时候再记录
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v;
stack<TreeNode*> s;
TreeNode* cur = root;
while(cur || !s.empty()){
if(cur){
v.push_back(cur->val);
s.push(cur);
cur = cur->left;
} else {
cur = s.top();
s.pop();
cur = cur->right;
}
}
return v;
}
};
后序遍历
因为后序遍历的压栈顺序是左-右-根，由于先遍历完左子树，然后遍历完右子树，然后才能处理当前节点，为了和之前的代码的结构保持一致，我们可以反向处理，也就是按根-右-左的顺序压栈，
结果反向输出即可
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> v;
stack<TreeNode*> s;
TreeNode* cur = root;
while(cur || !s.empty()){
if(cur){
v.push_back(cur->val);
s.push(cur);
cur = cur->right;
} else {
cur = s.top();
s.pop();
cur = cur->left;
}
}
reverse(v.begin(), v.end()); // 反向输出结果
return v;
}
};
Morris Traversal
线索二叉树，O(n)时间，常数空间
Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）
就是当前节点的中序遍历前驱节点，如果此前驱节点的右指针为空，则将此前驱节点的右指针指向当前节点
当寻找当前节点的中序遍历前驱节点时，发现能循环到自己，说明左子树已经遍历完，需要遍历右子树
中序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
TreeNode* cur, *prev;
vector<int> v;
cur = root;
prev = nullptr;
while(cur){
if(cur->left == nullptr){
v.push_back(cur->val);
cur = cur->right;
} else {
prev = cur->left;
while(prev->right != nullptr && prev->right != cur)
prev = prev->right;
if(prev->right == nullptr){
prev->right = cur;
cur = cur->left;
} else {
v.push_back(cur->val);
prev->right = nullptr;
cur = cur->right;
}
}
}
return v;
}
};
先序遍历
同样先序遍历与中序遍历相比也只需要改变一行代码的位置
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
TreeNode* cur, *prev;
vector<int> v;
cur = root;
prev = nullptr;
while(cur){
if(cur->left == nullptr){
v.push_back(cur->val);
cur = cur->right;
} else {
prev = cur->left;
while(prev->right != nullptr && prev->right != cur)
prev = prev->right;
if(prev->right == nullptr){
v.push_back(cur->val);
prev->right = cur;
cur = cur->left;
} else {
prev->right = nullptr;
cur = cur->right;
}
}
}
return v;
}
};
后序遍历
后序遍历需要反向输出cur->left到cur的中序前驱结点之间的路径
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void reverse_traverse_reverse(TreeNode* cur, vector<int>& v){
TreeNode* prev = nullptr;
while(cur){
auto right = cur->right;
cur->right = prev;
prev = cur;
cur = right;
}
cur = prev;
prev = nullptr;
while(cur){
auto right = cur->right;
cur->right = prev;
v.push_back(cur->val);
prev = cur;
cur = right;
}
}
vector<int> postorderTraversal(TreeNode* root) {
TreeNode* cur, *prev;
vector<int> v;
cur = new TreeNode(-1);
prev = nullptr;
cur->left = root;
while(cur){
if(cur->left == nullptr){
cur = cur->right;
} else {
prev = cur->left;
while(prev->right != nullptr && prev->right != cur)
prev = prev->right;
if(prev->right == nullptr){
prev->right = cur;
cur = cur->left;
} else {
prev->right = nullptr;
reverse_traverse_reverse(cur->left, v);
cur = cur->right;
}
}
}
return v;
}
};
总结
三种遍历方式中，后序遍历的处理比较麻烦，但是无论是使用递归栈，非递归栈还是Morris Traversal，代码的结构都是一样的，中序和前序甚至只有一行代码位置的差别
使用栈的版本中，最坏空间复杂度为O（n）链型，平均空间复杂度为O（lgn）
Morris Traversal空间复杂度为O(1)