【C++二叉树】进阶OJ题
目录
- 【C++二叉树】进阶OJ题
- 1.二叉树的层序遍历II
- 示例代码
- 解题思路
- 2.二叉搜索树与双向链表
- 示例代码
- 解题思路
- 3.从前序与中序遍历序列构造二叉树
- 示例代码
- 解题思路
- 4.从中序与后序遍历序列构造二叉树
- 示例代码
- 解题思路
- 5.二叉树的前序遍历(非递归迭代实现)
- 示例代码
- 解题思路
- 6.二叉树的中序遍历(非递归迭代实现)
- 示例代码
- 解题思路
- 7二叉树的后序遍历(非递归迭代实现)
- 示例代码
- 解题思路
作者:爱写代码的刚子
时间:2023.9.6
前言:本篇博客总结了一些二叉树有关的一些中等难度OJ题,总结这些题的解题思路
1.二叉树的层序遍历II
题目链接
示例代码
class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> vv;if(!root){return vv;}queue<TreeNode*> q;q.push(root);while(!q.empty()){int curlevel = q.size();vv.push_back(vector<int> ());while(curlevel--){TreeNode *front=q.front();vv.back().push_back(front->val);q.pop();if(front->left){q.push(front->left);}if(front->right){q.push(front->right);}}}reverse(vv.begin(),vv.end());return vv;}
};
解题思路
-
选择使用队列来实现
-
注意这里使用变量curlevel来记录每层的元素个数,并且第二个while循环中需要curlevel来计数,因为题目中要求返回 vector<vector>,所以记录每层的元素个数是必要的。
-
由于题目要求返回自底向上的层序遍历,所以我们还需要reverse函数将vector<vector>容器进行反转。
2.二叉搜索树与双向链表
题目链接
示例代码
class Solution {
public:void test(TreeNode* cur,TreeNode*& prev){if(cur==nullptr){return;}test(cur->left,prev);cur->left=prev;if(prev)//注意prev可能为nullptr{prev->right=cur;}prev=cur;test(cur->right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode*prev=nullptr;test(pRootOfTree,prev);TreeNode* leftover=pRootOfTree;while(leftover&&leftover->left){leftover=leftover->left;}return leftover;}
};
解题思路
- 采用中序遍历
- 由于二叉树遍历的特殊性,我们无法找到下一个遍历的对象,所以我们设立新旧指针:cur和prev,由于根节点prev未知,所以我们传入nullptr
- 我们让cur指针先走,对旧节点的指针朝向进行修改(prev的left和right指针)
- 如图:
本质其实就是让cur先走,记录先前节点(prev),并修改先前节点的指针朝向。
3.从前序与中序遍历序列构造二叉树
题目链接
示例代码
class Solution {
public:TreeNode* test(vector<int>& preorder, vector<int>& inorder,int begini,int& prei,int endi){if(begini>endi){return nullptr;}TreeNode* root=new TreeNode(preorder[prei]);int rooti=begini;while(rooti<=endi){if(preorder[prei]==inorder[rooti]){break;}else{++rooti;}}++prei;root->left=test(preorder, inorder,begini,prei,rooti-1);root->right=test(preorder, inorder,rooti+1,prei,endi);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i=0;return test(preorder,inorder,0,i,preorder.size()-1);}
};
解题思路
-
前序遍历可以确定根节点的位置
-
确定了根再去中序遍历里找到对应的根
-
两者遍历的图示:
-
观察图示结构,我们可以将前序遍历中的数据从左到右进行遍历,一次将遍历的节点作为根节点
-
观察图示结构,我们利用前序遍历中定的根节点在中序遍历中找到对应的位置,用中序遍历的结构来进行递归(类似分治)
-
递归的结束条件就是递归到子叶节点时,子叶节点再进行递归,递归区间有误。(begini>endi)
4.从中序与后序遍历序列构造二叉树
题目链接
示例代码
class Solution {
public:TreeNode*test(vector<int>& inorder, vector<int>& postorder,int begini,int& prei,int endi){if(begini>endi){return nullptr;}TreeNode*root=new TreeNode(postorder[prei]);int rooti=endi;while(rooti>=begini){if(inorder[rooti]==postorder[prei]){break;}--rooti;}--prei;root->right=test(inorder, postorder,rooti+1,prei,endi);root->left=test(inorder, postorder,begini,prei,rooti-1);//root->right=test(inorder, postorder,rooti+1,prei,endi);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int i=postorder.size()-1;return test(inorder, postorder,0,i,i);}
};
解题思路
-
思路与《从中序与后序遍历序列构造二叉树》类似,先画图:
-
我们发现与《从中序与后序遍历序列构造二叉树》这道题中的结构类似,所以考虑后序遍历序列从右往左遍历,依次将访问的节点作为根节点
-
注意!后序遍历中访问完根节点后访问的是右节点,所以我们应先构造右子树,将《从中序与后序遍历序列构造二叉树》题中的示例代码中两个递归入口交换顺序即可
5.二叉树的前序遍历(非递归迭代实现)
题目链接
示例代码
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> st;TreeNode* tmp=root;while(tmp||!st.empty()){while(tmp){v.push_back(tmp->val);st.push(tmp);tmp=tmp->left;}tmp=st.top()->right;st.pop();}return v;}
};
解题思路
- 使用vector和stack
- 先将二叉树最左边的节点push进栈,将节点储存的值push_back进vector
- 再取出栈顶元素,控制指针进入栈顶元素节点的右子树,并pop该栈顶元素,重复以上步骤
- 图示:
6.二叉树的中序遍历(非递归迭代实现)
题目链接
示例代码
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur=root;while(cur||!st.empty()){while(cur){st.push(cur);cur=cur->left;}TreeNode* top=st.top();v.push_back(top->val);cur=top->right;st.pop();}return v;}
};
解题思路
过程与前序遍历类似,只是访问的时机不同,中序遍历要在所有左子树push进栈后再进行访问,并pop栈顶元素
7二叉树的后序遍历(非递归迭代实现)
题目链接
示例代码
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;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){prev=top;v.push_back(top->val);st.pop();}else{cur=top->right;}}return v;}
};
解题思路
- 我们需要设定访问时机,当右子树已经访问完了或者没有右子树时进行访问。
- 如何判读右子树是否访问完了:要引入prev指针记录上一个访问的节点,判断prev是否等于当前节点(top)的右子树。
- 注意这里使用的是if…else语句,并不是无脑
cur=top->right