提示网站正在建设中,百度互联网营销顾问,天津建设工程信息网投标报名平台,做门户网站开发的技术目录
一、根据二叉树创建字符串
二、二叉树的层序遍历
三、二叉树的层序遍历 II
四、二叉树的最近公共祖先
五、二叉搜索树与双向链表
六、从前序与中序遍历序列构造二叉树
七、从中序与后序遍历序列构造二叉树 一、根据二叉树创建字符串
606. 根据二叉树创建字符串 - …目录
一、根据二叉树创建字符串
二、二叉树的层序遍历
三、二叉树的层序遍历 II
四、二叉树的最近公共祖先
五、二叉搜索树与双向链表
六、从前序与中序遍历序列构造二叉树
七、从中序与后序遍历序列构造二叉树 一、根据二叉树创建字符串
606. 根据二叉树创建字符串 - 力扣LeetCode
解题思路本题在递归前序遍历二叉树的同时要注意的省略这时就有了三种情况 如果当前节点没有孩子我们不需要在节点后面加上任何括号 如果当前节点只有左孩子我们在递归时只需要在左孩子的结果外加上一层括号而不需要给右孩子加上任何括号 如果当前节点只有右孩子我们在递归时需要先加上一层空的括号 ‘()’ 表示左孩子为空再对右孩子进行递归并在结果外加上一层括号
解题代码
class Solution {
public:string tree2str(TreeNode* root) {if(rootnullptr)return ;string strto_string(root-val);if(root-left||root-right)//有左孩子或者无左孩子有右孩子{str(;strtree2str(root-left);str);}if(root-right)//有右孩子{str(;strtree2str(root-right);str);}return str;}
}; 二、二叉树的层序遍历
102. 二叉树的层序遍历 - 力扣LeetCode
解题思路本题为了达到层序遍历我们需要用到一个队列来保存每一层的节点将将根节点入队列每次出队列时都要将其孩子节点入队列
还要有一个变量来记录每一层节点的个数当该变量不为0时需要将节点出队列所出节点都属于同一层的元素每出一个节点将其减1。当该变量为0时队列中都是上一层节点的孩子节点所以都属于同一层节点这时将变量置为队列中元素个数继续将节点出队列即可直到队列为空
解题代码
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* q;int levelsize0;if(root)//根节点入队列{q.push(root);levelsize1;}vectorvectorint vv;while(!q.empty()){vectorint v;//记录每一层的数据while(levelsize--)//将上一层节点出队列的同时将其孩子节点都入队列{TreeNode* frontq.front();q.pop();v.push_back(front-val);if(front-left)q.push(front-left);if(front-right)q.push(front-right);}vv.push_back(v);//将遍历完的一层数据存入levelsizeq.size();}return vv;}
}; 三、二叉树的层序遍历 II
107. 二叉树的层序遍历 II - 力扣LeetCode
解题思路该题是上题的变形题很多同学容易在这题中想的过多这一题想要的结果是上题的结果的逆置所以按上题思路处理最后将其结果逆置一下即可
解题代码
class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {queueTreeNode* q;int levelsize0;if(root)//根节点入队列{q.push(root);levelsize1;}vectorvectorint vv;while(!q.empty()){vectorint v;//记录每一层的数据while(levelsize--)//将上一层节点出队列的同时将其孩子节点都入队列{TreeNode* frontq.front();q.pop();v.push_back(front-val);if(front-left)q.push(front-left);if(front-right)q.push(front-right);}vv.push_back(v);//将遍历完的一层数据存入levelsizeq.size();}reverse(vv.begin(),vv.end());//将结果逆置return vv;}
}; 四、二叉树的最近公共祖先
236. 二叉树的最近公共祖先 - 力扣LeetCode
解题思路对于该题我们需要了解两个节点最近公共祖先的特性即这两个节点分别在最近公共祖先节点的左右子树所以我们只要找到满足该条件的节点就找到了最近公共祖先节点
解题代码
class Solution {
public:bool IsIntree(TreeNode* root, TreeNode* x){if(rootnullptr)return false;if(rootx)return true;return IsIntree(root-left,x)||IsIntree(root-right,x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(rootp||rootq)return root;bool pInleftIsIntree(root-left,p);bool pInright!pInleft;bool qInleftIsIntree(root-left,q);bool qInright!qInleft;if((pInrightqInleft)||(pInleftqInright)){return root;}else if(pInleftqInleft){return lowestCommonAncestor(root-left,p,q);}else{return lowestCommonAncestor(root-right,p,q);}}
};
但是该方法最坏情况下的时间复杂度为O(N^2)运行时长并不理想 那下面我们换个思路来优化一下我们可以记录从根节点到两个要查找节点的路径从而将其转换为链表相交问题对于链表的相交问题我们之前在LeetCode和牛客网经典链表题目合集 讲过对于路径的存储我们可以用到栈来记录最终找到共同的最近祖先节点
class Solution {
public:bool GetPath(TreeNode* root, TreeNode* x,stackTreeNode* s){if(rootnullptr)return false;s.push(root);if(rootx)return true;if(GetPath(root-left,x,s)||GetPath(root-right,x,s))return true;s.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stackTreeNode* pPath,qPath;GetPath(root,p,pPath);GetPath(root,q,qPath);while(pPath.size()!qPath.size()){if(pPath.size()qPath.size())pPath.pop();elseqPath.pop();}while(pPath.top()!qPath.top()){pPath.pop();qPath.pop();}return pPath.top();}
};
这样子时间复杂度就降到了O(N) 五、二叉搜索树与双向链表
二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
解题思路在该题中需要利用二叉搜索树中序遍历的结果是升序的所以我们在中序遍历时修改所在节点与前驱节点的指针指向即可用cur指针表示当前节点用prev指针表示中序遍历时当前节点的上一个遍历节点使cur指针的左孩子
下面是一个二叉搜索树中序遍历时修改当前节点和前驱节点的指针指向的演示 解题代码
class Solution {
public:void InOrder(TreeNode* cur,TreeNode* prev){if(curnullptr)return;InOrder(cur-left,prev);cur-leftprev;if(prev)prev-rightcur;//让前驱节点指针的右孩子指向当前节点prevcur;//更新前驱节点指针位置InOrder(cur-right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTreenullptr)return nullptr;TreeNode* prevnullptr;InOrder(pRootOfTree,prev);//中序遍历的同时修改二叉树节点指针的指向TreeNode* headpRootOfTree;//pRootOfTree并非链表的头节点需要找到头节点后返回while(head-left){headhead-left;}return head;}
}; 六、从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode
解题思路
对于任意一颗树而言前序遍历的形式总是 [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ] 即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是 [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ] 只要我们在中序遍历中定位到根节点那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的因此我们就可以对应到前序遍历的结果中对上述形式中的所有左右括号进行定位
这样以来我们就知道了左子树的前序遍历和中序遍历结果以及右子树的前序遍历和中序遍历结果我们就可以递归地对构造出左子树和右子树再将这两颗子树接到根节点的左右位置
解题代码
class Solution {
public:TreeNode* _buildTree(vectorint preorder, vectorint inorder,int begini,int endi,int n) {if(beginiendi)return nullptr;TreeNode* newnodenew TreeNode(preorder[n]);//先利用先序遍历确定根节点int rootibegini;while(rootiendi)//找到确定的根节点在中序遍历中的位置{if(inorder[rooti]preorder[n])break;elserooti;}n;newnode-left_buildTree(preorder,inorder,begini,rooti-1,n);//将剩下的左区间的节点连接到左子树上newnode-right_buildTree(preorder,inorder,rooti1,endi,n);//将剩下的右区间的节点连接到右子树上return newnode;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int n0;return _buildTree(preorder,inorder,0,preorder.size()-1,n);}
}; 七、从中序与后序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树 - 力扣LeetCode
解题思路该题和上一题是同类型题我们使用后序遍历的逆序来确定根节点再在中序遍历中找到其对应的节点再递归地对构造出右子树和左子树后序遍历的逆序是相当于先遍历右子树的前序遍历所以我们先要构建右子树再构建左子树
解题代码
class Solution {
public:TreeNode* _buildTree(vectorint inorder,vectorint postorder,int begini,int endi,int n) {if(beginiendi)return nullptr;TreeNode* newnodenew TreeNode(postorder[n]);//先利用后序遍历确定根节点int rootibegini;while(rootiendi)//找到确定的根节点在中序遍历中的位置{if(inorder[rooti]postorder[n])break;elserooti;}--n;newnode-right_buildTree(inorder,postorder,rooti1,endi,n);//将剩下的右区间的节点连接到右子树上newnode-left_buildTree(inorder,postorder,begini,rooti-1,n);//将剩下的左区间的节点连接到左子树上return newnode;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {int ninorder.size()-1;return _buildTree(inorder,postorder,0,inorder.size()-1,n);}
};
