园林绿化网站建设,如何注册微信小程序商家,用jquery做网站,烟台网站制作软件做每件事之前都心存诚意, 就会事半功倍. 目录 前言1. 根据二叉树创建字符串2. 二叉树的层序遍历Ⅰ3. 二叉树的层序遍历Ⅱ4. 二叉树的最近公共祖先5. 二叉搜索树与双向链表6. 根据一棵树的前序遍历与中序遍历构造二叉树7. 根据一棵树的中序遍历与后序遍历构造二叉树8. 二叉树的…做每件事之前都心存诚意, 就会事半功倍. 目录 前言1. 根据二叉树创建字符串2. 二叉树的层序遍历Ⅰ3. 二叉树的层序遍历Ⅱ4. 二叉树的最近公共祖先5. 二叉搜索树与双向链表6. 根据一棵树的前序遍历与中序遍历构造二叉树7. 根据一棵树的中序遍历与后序遍历构造二叉树8. 二叉树的前序遍历非递归迭代实现9. 二叉树中序遍历 非递归迭代实现10. 二叉树的后序遍历 非递归迭代实现 前言
一些面试中可能会遇到的二叉树的进阶题目, 这些题目我们也需要进行掌握.
博客主页: 酷酷学!!!
更多好文, 持续关注 正文开始
1. 根据二叉树创建字符串
题目链接: 根据二叉树创建字符串
题目描述: 题目思路:
根据前序遍历创建二叉树, 再递归子树之前需要加括号, 但是题目要求省略不必要的括号, 通过观察可发现
左右子树都为空, 省略括号右子树为空,省略括号左为空, 右不为空, 不能省略括号
每次递归之前加上条件即可, 不要忘记将整型转化为字符串, 字符串不能直接相加整型数据
题目代码:
/*** 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:string tree2str(TreeNode* root) {string str;if(root nullptr)return str;str to_string(root-val);//两个都为空就省略括号if(root-left || root-right){str(;strtree2str(root-left);str);}//右子树存在则都要括号if(root-right){str(;strtree2str(root-right);str);}return str;}
};2. 二叉树的层序遍历Ⅰ
题目链接: 二叉树的层序遍历Ⅰ
题目描述: 题目思路:
我们在层序遍历过程中增加一个levelSize记录每层的数据个数树不为空的情况下第1层levelSize1循环控制第1层出完了第2层就都进队列了队列中size就是第2层的数据个数。以此内推假设levelSize为第n层的数据个数因为层序遍历思想为当前层结点出队列带入下一层结点(也就是子结点)循环控制第n层数据出完了那么第n1结点都进队列了队列size就是下⼀层的levelSize。
题目代码:
/*** 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:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint vv;queueTreeNode* q;int levelsize 1;if(root nullptr) return vv;q.push(root);while(levelsize){vectorint v;while(levelsize--){TreeNode* front q.front();v.push_back(front-val);if(front-left) q.push(front-left);if(front-right) q.push(front-right);q.pop();}vv.push_back(v);levelsize q.size();}return vv;}
};3. 二叉树的层序遍历Ⅱ
题目链接: 二叉树的层序遍历Ⅱ
题目描述: 题目思路:
107的第二个题目思路跟上题102⼀样只⼆维数组逆置⼀下就可以得到结果。
题目代码:
/*** 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:vectorvectorint levelOrderBottom(TreeNode* root) {vectorvectorint vv; int levelsize 0;queueTreeNode* q;if(root){q.push(root);levelsize 1;}while(levelsize0){vectorint v;while(levelsize--){TreeNode* front q.front();q.pop();v.push_back(front-val);if(front-left) q.push(front-left);if(front-right) q.push(front-right);}levelsize q.size();vv.push_back(v);}reverse(vv.begin(),vv.end());return vv;}
};4. 二叉树的最近公共祖先
题目链接: 二叉树的最近公共祖先
题目描述: 题目思路: 思路1仔细观察⼀下两个结点最近公共祖先的特征就是⼀个结点在最近公共祖先的左边⼀个结点在最近公共祖先的右边。⽐如6和4的公共祖先有5和3但是只有最近公共祖先5满⾜6在左边4在右边。
思路2如果能求出两个结点到根的路径那么就可以转换为链表相交问题。如6到根3的路径为6-5-34到根3的路径为4-2-5-3那么看做两个链表找交点交点5就是最近公共祖先。
思路二时间复杂度更好一点,但是空间复杂度大一点
题目代码:
思路一:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool IsInTree(TreeNode* t,TreeNode* x){if(t nullptr)return false;return t x || IsInTree(t-left,x) || IsInTree(t-right,x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root nullptr)return nullptr;if(root p || root q)return root;//自此开始要么都在左,要么都在右bool pInleft IsInTree(root-left,p);bool pInright !pInleft;bool qInleft IsInTree(root-left,q);bool qInright !qInleft;if((qInleftpInright) || (qInrightpInleft)) return root;else if(pInleft qInleft) return lowestCommonAncestor(root-left,p,q);else return lowestCommonAncestor(root-right,p,q);}
};思路二:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool ancestor(TreeNode* root,TreeNode* node,stackTreeNode* s){if(root nullptr) return false;s.push(root);if(root node) return true;if(ancestor(root-left,node,s)) return true;if(ancestor(root-right,node,s)) return true;s.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stackTreeNode* pstack;stackTreeNode* qstack;ancestor(root,p,pstack);ancestor(root,q,qstack);while(pstack.size()qstack.size()){pstack.pop();}while(qstack.size()pstack.size()){qstack.pop();}while(qstack.top()!pstack.top()){pstack.pop();qstack.pop();}return qstack.top();}
};5. 二叉搜索树与双向链表
题目链接: 二叉搜索树与双向链表
题目描述: 题目思路:
搜索⼆叉树⾛中序是有序的本题⽬要求原地修改也就是不能创建新的结点。
思路1中序遍历搜索⼆叉树遍历顺序是有序的将⼆叉树的结点指针放到⼀个vector中再把前后结点的链接关系进⾏修改。这个思路最简单但是需要消耗O(N)的空间复杂度。
思路2依旧中序遍历搜索⼆叉树遍历顺序是有序的遍历过程中修改左指针为前驱和右指针为后继指针。记录⼀个cur和prevcur为当前中序遍历到的结点prev为上⼀个中序遍历的结点cur-left指向prevcur-right⽆法指向中序下⼀个因为不知道中序下⼀个是谁但是prev-right指向cur也就是说每个结点的左是在中遍历到当前结点时修改指向前驱的但是当前结点的右是在遍历到下⼀个结点时修改指向后继的。
代码如下:
/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:void InOrderConvert(TreeNode* cur,TreeNode* prev){if(curnullptr) return;InOrderConvert(cur-left,prev);cur-left prev;if(prev)prev-right cur;prev cur;InOrderConvert(cur-right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTreenullptr) return nullptr;TreeNode* prev nullptr;InOrderConvert(pRootOfTree,prev);TreeNode* head pRootOfTree;while(head-left){head head-left;}return head;}
};6. 根据一棵树的前序遍历与中序遍历构造二叉树
题目链接: 根据一棵树的前序遍历与中序遍历构造二叉树
题目描述: 题目思路:
前序的⽅式构建树前序确定当前构建树的根根分割中序的左⼦树和右⼦树再分别递归构建左⼦树和右⼦树。
/*** 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:TreeNode* build(vectorint preorder,vectorint inorder,int prei,int inbegin,int inend){if(inbegininend) return nullptr;//前序确定根TreeNode* root new TreeNode(preorder[prei]);//中序分割左右子树int rooti inbegin;while(rooti inend){if(preorder[prei] inorder[rooti])break;elserooti;}prei;root-left build(preorder,inorder,prei,inbegin,rooti-1);root-right build(preorder,inorder,prei,rooti1,inend);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int i 0;return build(preorder,inorder,i,0,inorder.size()-1);}
};7. 根据一棵树的中序遍历与后序遍历构造二叉树
题目链接: 根据一棵树的中序遍历与后序遍历构造二叉树
题目描述: 题目思路:
此题跟第六题差不多, 区别在于后续来确定根, 与上题相反, 且后续遍历的顺序是 左 右 根, 所以第二次取到是右子树的根, 故创建完根之后, 先创建右子树, 再创建根
题目代码:
/*** 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:TreeNode* build(vectorint inorder, vectorint postorder,int post,int inbegin,int inend){if(inbegininend) return nullptr;TreeNode* newnode new TreeNode(postorder[post]);int rooti inbegin;while(rootiinend){if(postorder[post] inorder[rooti])break;elserooti;}post--;newnode-right build(inorder,postorder,post,rooti1,inend);newnode-left build(inorder,postorder,post,inbegin,rooti-1);return newnode;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {int post postorder.size()-1;return build(inorder,postorder,post,0,inorder.size()-1);}
};8. 二叉树的前序遍历非递归迭代实现
题目链接: 二叉树的前序遍历
题目描述: 题目思路:
在二叉树初阶刷题阶段, 我们已经实现了前序遍历的递归实现, 但是递归层数多会造成栈溢出, 所以对于非递归的实现, 我们也要掌握, 其实原理也很简单, 就是模拟递归实现的过程, 先创建一个栈, 用于记录根模拟递归的过程, 遍历左节点, 遍历之前先入栈, 此题前序遍历, 所以直接将此节点的val也插入到vector中, 直到遍历到nullptr,次时说明左子树已全部遍历完, 接着去栈顶元素, 出栈顶元素, 并且将栈顶元素的right赋值给cur,进行下一次的循环遍历, 直至栈为空, 结束的条件cur不为空说明还有右子树需要遍历, 栈不为空说明还有左子树需要遍历右子树.
代码实现:
/*** 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:
//非递归前序遍历vectorint preorderTraversal(TreeNode* root) {vectorint v;TreeNode* cur root;stackTreeNode* snode;while(cur || !snode.empty()){while(cur){v.push_back(cur-val);snode.push(cur);cur cur-left;}TreeNode* top snode.top();snode.pop();cur top-right;}return v;}
};9. 二叉树中序遍历 非递归迭代实现
题目连接: 二叉树的中序遍历
题目描述: 题目思路:
本题要求中序遍历, 基本思路与前序遍历差不多, 模拟递归的实现过程, 只不过, 本次我们左子树入栈不要进行访问, 而是遍历到左子树为nullptr时, 回退的过程在进行访问, 然后在访问右子树, 右子树也是一样的操作, 遇到不为空先不访问, 先入栈,直到栈为空时, 在进行访问, 此时访问的效果就达到 左 根 右.
代码实现:
/*** 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:vectorint inorderTraversal(TreeNode* root) {vectorint v;stackTreeNode* snode;TreeNode* cur root;while(cur || !snode.empty()){while(cur){snode.push(cur);cur cur-left;}TreeNode* top snode.top();v.push_back(top-val);cur top-right;snode.pop();}return v;}
};10. 二叉树的后序遍历 非递归迭代实现
题目连接: 二叉数的后序遍历
题目描述: 题目思路:
还是双循环模拟递归的实现过程, 遇到节点先不放问, 先入栈, 但是我们需要先访问左, 在访问右, 最后访问根, 所以左子树遍历到空之后, 取栈顶元素访问右子树, 如果右子树为根的情况我们才能访问, 访问完之后, 出栈, 在取栈顶元素, 问题就来了, 这时又会取到栈顶元素的右子树, 那我们是否还需要再进去访问呢, 如果访问过了我们就不要访问了, 直接访问此节点, 没访问过在进行访问, 不然会陷入死循环, 这是我们额为创建一个指针来记录上一次出栈的节点, 也就是上一次访问过的节点, 如果为top-right那么就不用进入循环了, 直接pop并直接访问该节点即可, 通过模拟我们可以发现, 其实不管怎么样, 后序遍历一定是先访问的是右子树为空的那个节点.
代码实现:
/*** 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:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* snode;TreeNode* cur root;TreeNode* prev nullptr;vectorint v;while(cur || !snode.empty()){while(cur){snode.push(cur);cur cur-left;}TreeNode* top snode.top();if(top-right nullptr || prev top-right){v.push_back(top-val);prev top;snode.pop();}else{cur top-right;}}return v;}
};完 这些进阶题目我们也需要进行掌握, 这样才能运筹帷幄, 创作不易 感谢点赞关注!!!
