代码随想录 二叉树 test 2
二叉树的非递归遍历
先序
方法一:
先保存根节点，用来之后找到右子树(利用栈来回溯到根，进而找到右子树)
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res; //存遍历序列
stack<TreeNode*> stk;
TreeNode* p = root;
while(p || !stk.empty()){
if(p != nullptr){
res.push_back(p->val); //访问根节点
stk.push(p);
p = p->left; //移动到左子树
}else{ //如果左子树为空，就需要访问上一个结点的右子树
p = stk.top();
stk.pop();
p = p->right;
}
}
return res;
}
};方法二:
不用回溯，利用栈的先进后出性质，先将右子树入栈，再将左子树入栈，实现根左右。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if(!root) return {};
vector<int> res; //存遍历序列
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()){
TreeNode* p = stk.top();
stk.pop();
res.push_back(p->val); //根
if(p->right) stk.push(p->right); //将非空的右孩子压栈
if(p->left) stk.push(p->left); //将非空的左孩子压栈
}
return res;
}
};方法三:统一迭代法
每次以根节点为处理对象，如果当前遍历的结点非空，则按照右左根顺序，将三个结点都压入栈中，在压入根节点之后继续压入空指针，因此处理顺序与出栈顺序对应。如果为空，则当前该结点需要输出。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res; //存遍历序列
if(!root) return res;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()){
TreeNode* p = stk.top();
if(p != nullptr){
stk.pop();
if(p->right) stk.push(p->right); //右
if(p->left) stk.push(p->left); //左
stk.push(p); //中
stk.push(nullptr); //标记在空结点之下即为要处理的结点
}else{
stk.pop(); //弹出空结点
p = stk.top(); //访问要处理的结点
stk.pop(); //弹出已处理好的结点
res.push_back(p->val);
}
}
return res;
}
};中序
方法一
与先序方法一类似，将访问结点操作放在遍历到当前最左结点之后。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res; //存遍历序列
stack<TreeNode*> stk;
TreeNode* p = root;
while(p || !stk.empty()){
if(p != nullptr){
stk.push(p);
p = p->left; //移动到左子树
}else{ //如果左子树为空，就需要访问上一个结点的右子树
p = stk.top();
stk.pop();
res.push_back(p->val); //访问左
p = p->right;
}
}
return res;
}
};方法二:统一迭代法
只需将先序中的统一迭代法，按照右根左入栈即可。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res; //存遍历序列
if(!root) return res;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()){
TreeNode* p = stk.top();
if(p != nullptr){
stk.pop();
if(p->right) stk.push(p->right); //右
stk.push(p); //中
stk.push(nullptr); //标记在空结点之下即为要处理的结点
if(p->left) stk.push(p->left); //左
}else{
stk.pop(); //弹出空结点
p = stk.top(); //访问要处理的结点
stk.pop(); //弹出已处理好的结点
res.push_back(p->val);
}
}
return res;
}
};后序
方法一
改写先序方法一，由于遍历顺序要求是左右根，因此回溯的情况既可能是遍历完左子树也可能是遍历完右子树。如果是遍历完左子树且有右子树且右子树未被遍历过，则需要继续遍历右子树，如果是遍历完右子树，则此时栈顶元素即为当前最右，需要进行处理，处理完最右结点需要回溯到根，因此需要将当前指针置为空，在下一次循环就可以取出栈顶根。由上可知需要标记结点是否被遍历过，因此需要一个指针r记录上一个遍历过的结点。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res; //存遍历序列
stack<TreeNode*> stk;
TreeNode* p = root;
TreeNode* r = nullptr;
while(p || !stk.empty()){
if(p != nullptr){
stk.push(p);
p = p->left; //移动到左子树
}else{ //如果左子树为空，就需要检查右子树状态
p = stk.top();
if(p->right && r != p->right){ //如果有右子树且未被遍历过
p = p->right;
}else{ //否则应该处理栈顶元素
p = stk.top();
stk.pop();
res.push_back(p->val); //处理栈顶
r = p; //标记此结点已被处理
p = nullptr;
}
}
}
return res;
}
};方法二:改写先序方法二+反转
先序方法二颠倒左右子树入栈顺序实现根右左，再进行反转，变成左右根。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
if(!root) return {};
vector<int> res; //存遍历序列
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()){
TreeNode* p = stk.top();
stk.pop();
res.push_back(p->val); //根
if(p->left) stk.push(p->left); //将非空的左孩子压栈
if(p->right) stk.push(p->right); //将非空的右孩子压栈
}
reverse(res.begin(), res.end()); //反转数组
return res;
}
};方法三:统一迭代法
按照根右左顺序入栈
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res; //存遍历序列
if(!root) return res;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()){
TreeNode* p = stk.top();
if(p != nullptr){
stk.pop();
stk.push(p); //中
stk.push(nullptr); //标记在空结点之下即为要处理的结点
if(p->right) stk.push(p->right); //右
if(p->left) stk.push(p->left); //左
}else{
stk.pop(); //弹出空结点
p = stk.top(); //访问要处理的结点
stk.pop(); //弹出已处理好的结点
res.push_back(p->val);
}
}
return res;
}
};