非递归实现二叉树的前序、中序、后序遍历
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
目录
非递归遍历需要借助栈。
非递归实现二叉树的前序遍历
前序遍历二叉树的前序遍历按照访问根节点——左子树——右子树的方式遍历这棵树而在访问左子树或者右子树的时候我们按照同样的方式遍历直到遍历完整棵树。
1. 如果树为空直接返回
2. 如果树非空从根节点位置开始遍历因为前序遍历规则根节点、左子树、右子树
a. 沿着根节点一直往左走将所经过路径中的节点依次入栈并访问。
b. 取栈顶元素该元素取到后其左子树要么为空要么已经遍历可以直接遍历该节点对于该节点其左子树已经遍历该节点也已经遍历剩余其右子树没有遍历将其左子树当成一棵新的树开始遍历继续a步骤
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v;
stack<TreeNode*> st;
TreeNode*cur = root;
while(cur || !st.empty())
{
//循环每走一次迭代就是在访问一棵树的开始
//访问左路节点左路节点入栈
while(cur)
{
st.push(cur);
v.push_back(cur->val);
cur = cur->left;
}
//取出节点访问右路节点
TreeNode* top = st.top();
st.pop();
//子问题形式访问右子树
cur = top->right;
}
return v;
}非递归实现二叉树的中序遍历
中序遍历按照访问左子树——根节点——右子树的方式遍历这棵树而在访问左子树或者右子树的时候我们按照同样的方式遍历直到遍历完整棵树。
中序遍历中从栈中弹出的节点其左子树是访问完了可以直接访问该节点然后接下来访问右子树。
1. 如果树为空直接返回
2. 如果树非空从根节点位置开始遍历因为前序遍历规则左子树、根节点、右子树
a. 沿着根节点一直往左走将所经过路径中的节点依次入栈并访问。
b. 取栈顶元素该元素取到后其左子树要么为空要么已经遍历可以直接遍历该节点对于该节点其左子树已经遍历该节点也已经遍历剩余其右子树没有遍历将其左子树当成一棵新的树开始遍历继续a步骤
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
stack<TreeNode*> st;
TreeNode*cur = root;
while(cur || !st.empty())
{
while(cur)
{
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top();
st.pop();
v.push_back(top->val);
cur = top->right;
}
return v;
}非递归实现二叉树的后序遍历
后序遍历按照访问左子树——右子树——根节点的方式遍历这棵树而在访问左子树或者右子树的时候我们按照同样的方式遍历直到遍历完整棵树。
后序遍历中从栈中弹出的节点我们只能确定其左子树肯定访问完了但是无法确定右子树是否访问过。因此我们在后序遍历中引入了一个prev来记录历史访问记录。
1. 如果树为空直接返回
2. 如果树非空从根节点位置开始遍历但此时根节点不能遍历因为后序遍历规则左子树、右子树、根节点
a. 沿着根节点一直往左走将所经过路径中的节点依次入栈
b. 取栈顶元素该元素取到后其左子树要么为空要么已经遍历但是此时该节点不能遍历除非其右子树不存在或者其右子树已经遍历才可以遍历该节点如果该节点右子树没有遍历将其右子树作为一棵新的二叉树遍历继续a
- 当访问完一棵子树的时候我们用prev指向该节点。
- 这样在回溯到父节点的时候我们可以依据prev是指向左子节点还是右子节点来判断父节点的访问情况。
vector<int> postorderTraversal(TreeNode* root) {
vector<int> v;
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)
{
v.push_back(top->val);
//更新历史访问记录这样回溯的时候父节点可以由此判断右子树是否访问完成
prev = top;
st.pop();
}
else
{
//右子树没有访问过访问右子树
cur = top->right;
}
}
return v;
}根据二叉树的前序和中序遍历结果还原二叉树
1. 从前序遍历结果中获取到树的根节点
2. 在中序遍历结果中确定根节点的位置按照该位置将中序遍历结果分为两部分
左半部分是根节点的左子树递归创建根节点的左子树
右半部分是根节点的右子树递归创建根节点的右子树
TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& previ,int inbegin,int inend) {
if(inbegin >inend)
return NULL;
TreeNode* root = new TreeNode(preorder[previ]);
int rooti = inbegin;
while(rooti <= inend)
{
if(inorder[rooti] == preorder[previ])
break;
else
++rooti;
}
++previ;
//[inbegin rooti-1] rooti [rooti+1,inend]
root->left = _buildTree(preorder,inorder,previ,inbegin,rooti-1);
root->right = _buildTree(preorder,inorder,previ,rooti+1,inend);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int previ = 0;
return _buildTree(preorder,inorder,previ,0,inorder.size()-1);
}根据二叉树的中序和后序遍历结果还原二叉树
1. 从后序遍历结果中获取到树的根节点注意后序遍历规则左子树、右子树、根节点因此应该从后往前获取根节点
2. 在中序遍历结果中确定根节点的位置按照该位置将中序遍历结果分为两部分
右半部分是根节点的右子树递归创建根节点的右子树---->注意先要还原根的右子树
左半部分是根节点的左子树递归创建根节点的左子树
TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder,int& posti,int inbegin,int inend) {
if(inbegin > inend)
return NULL;
TreeNode* root = new TreeNode(postorder[posti]);
int rooti = inbegin;
while(rooti <= inend)
{
if(postorder[posti] == inorder[rooti])
break;
else
++rooti;
}
--posti;
root->right = _buildTree(inorder,postorder,posti,rooti+1,inend);
root->left = _buildTree(inorder,postorder,posti,inbegin,rooti-1);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int posti = postorder.size()-1;
return _buildTree(inorder,postorder,posti,0,inorder.size()-1);
}