代码随想录 二叉树 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;}
};