Leetcode-二叉树的前,中,后序的非递实现
前序的非递归
借助力扣的题来实现前序遍历的非递归。前序的递归是先访问根节点,左子树,右子树。
虽然递归实现较简单,但是非递归的实现我们也要掌握。非递归实现要借助栈来显示,但是思想还是递归的思想。
实现思路:
1.先访问左路节点
2.访问左路结点的同时入栈
3.子问题的方式再去访问右子树
先画一手图:
动图演示(借用力扣官方的动图):
在附上代码:
/**
* 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) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res; //存val值
stack<TreeNode*>st;//定义一个栈
TreeNode* cur = root;//cur指向谁就开始访问谁
while(cur || !st.empty()) //当cur为空或者栈为空循环结束
{
while(cur)
{
res.push_back(cur->val);//把值存到vector
st.push(cur); //入栈
cur=cur->left;
}
TreeNode* top = st.top();//取栈顶结点
st.pop();
//访问右子树交给子问题的方式解决
cur=top->right;
}
//最后返回vector
return res;
}
};
中序的非递归
有了前序的基础的话,中序的非递归也就变得简单了。中序遍历是左子树,根节点,右子树。
先让左路结点入栈,入栈完毕,取栈顶元素访问。之后用同样的方法访问右子树。
画图分析:
动图(力扣的动图):
代码:
/**
* 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) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*>st;
TreeNode* cur = root;
while(cur || !st.empty())
{
while(cur)
{
st.push(cur);//现将结点入栈
cur=cur->left;
}
TreeNode* top = st.top();
res.push_back(top->val);//访问栈顶元素
st.pop();
cur=top->right;
}
return res;
}
};
后序的非递归
后序的遍历,左子树->右子树->根节点。左路结点先入栈,当右子树为空或右子树访问过了,栈顶结点出栈并访问。若栈顶结点的右子树还没访问,在用同样的方式访问右子树。
具体步骤:
1.左路结点入栈
2.观察栈顶结点
3.栈顶结点的右子树为空或者访问完右子树,访问栈顶结点。栈顶结点出栈,并记录栈顶结点
4.栈顶结点的右子树若没访问,则准备访问右子树
画图分析:
动图演示(取自力扣动图):
代码:
/**
* 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) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*>st;
TreeNode* cur = root;
TreeNode* prev = nullptr;
while(cur || !st.empty())
{
while(cur)
{
st.push(cur);//左路结点先入栈
cur = cur->left;
}
TreeNode* top = st.top();
//右子树为空,或者栈顶的右子树是根节点则可以访问根节点
if(top->right == nullptr || top->right == prev)
{
res.push_back(top->val);
st.pop();
prev = top;//记录栈顶结点
}
else
{
cur = top->right;
}
}
return res;
}
};