江苏建设招标网站,网站建设备案优化设,异度空间图书馆主题 wordpress,google浏览器官网入口本期#xff0c;将给大家带来的是关于 LeetCode 的关于二叉树的题目讲解。
目录
#xff08;一#xff09;606. 根据二叉树创建字符串
#x1f4a5;题意分析
#x1f4a5;解题思路
#xff08;二#xff09;102. 二叉树的层序遍历
#x1f4a5;题意分析
#…本期将给大家带来的是关于 LeetCode 的关于二叉树的题目讲解。
目录
一606. 根据二叉树创建字符串
题意分析
解题思路
二102. 二叉树的层序遍历
题意分析
解题思路
三236. 二叉树的最近公共祖先 题意分析
解题思路 一606. 根据二叉树创建字符串 首先第一道题是关于 二叉树创建字符串的题接下来我将一步步的分析带大家理解这道题 题目如下 输入root [1,2,3,4]
输出1(2(4))(3)
解释初步转化后得到 1(2(4)())(3()()) 但省略所有不必要的空括号对后字符串应该是1(2(4))(3) 。 输入root [1,2,3,null,4]
输出1(2()(4))(3)
解释和第一个示例类似但是无法省略第一个空括号对否则会破坏输入与输出一一映射的关系。
题意分析 首先我们还是先对题意进行简单的分析 我们可以发现他不是把所有的输出都给用括号括起来仔细观察发现而是有些直接省略了具体省略的有以下几种情况
1、左右都为空——省略2、左为空右不为空——不省略3、右为空左不为空——省略
但是大家仔细观察可以发现此时当我们按照上述方式去看示例时发现跟题意对不上。个人觉得应该是题当时弄错了本题的整体思路就如上述具体应该如下才对 总之大概意思就是根据题意给出的二叉树的我们按照合适的输出方案输出即可
解题思路
具体思路如下
我们可以使用递归的方法得到二叉树的前序遍历并且每次递归时加上相应的括号即可得到最终的结果。 1、如果当前节点没有孩子即左右都为空此时则不需要在节点后面加上任何括号 2、如果当前节点只有左孩子而右为空。那我们在递归时只需要在左孩子的结果外加上一层括号而不需要给右孩子加上任何括号 3、对应的如果当前节点只有右孩子而左为空。那当我们在递归时此时的括号就不难省略了。此时需要先加上一层空的括号表示左孩子为空再对右孩子进行递归并在结果外加上一层括号。 代码展示
class Solution {
public:string tree2str(TreeNode* root) {if(root nullptr)return ;//root-val不支持转成整形因此这里加上to_string 即可实现转成字符串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. 二叉树的层序遍历
题目如下 输入root [3,9,20,null,null,15,7]
输出[[3],[9,20],[15,7]]
示例 2
输入root [1]
输出[[1]]
示例 3
输入root []
输出[]
题意分析
本题的意思其实很简答就是根据给出的二叉树我们相当于层序遍历之后输出最后的结果即可解题思路 在这里我给出两种思路供大家参考 1、我们定义两个队列。
一个队列控制结点的指针然后去控制层序遍历另外一个队列则为一个整形控制层数即此时是第几层的在进行操作。图解 2、我们只定义一个队列。
我们也可以定义一个队列进行操作
此时我们还需要在定义一个变量设为【levelsize】。目的是为了控制二叉树一层一层的出
图解 代码展示
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* str;int levelsize0;if(root){str.push(root);levelsize1;}//控制每层的元素出队列vectorvectorintarry;while(!str.empty()){vectorintv;//levelsize 为几就表示需要出几次while(levelsize--){//先取对头的数据TreeNode* frontstr.front();str.pop();v.push_back(front-val);//左不为空把元素入队if(front-left)str.push(front-left);//右不为空把元素入队if(front-right)str.push(front-right);}//每层出的元素放到相应的数组中arry.push_back(v);levelsizestr.size();}return arry;}
};
最终结果三236. 二叉树的最近公共祖先
题目如下 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1
输出3
解释节点 5 和节点 1 的最近公共祖先是节点 3 。 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4
输出5
解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 题意分析
本题的大概意思就是题中给出两个节点在二叉树中我们去找到这两个节点的公共父结点输出即可解题思路
思路一 整体思路就是DFS求出p和q 的路径放到容器中转换成路径相交。 我们用栈来充当这个容器定义Ppath为当前节点左端的路径qpath为右端的节点路径
图解当我们成功的找到两端的路径之后接下来就是判断步奏了代码展示
class Solution {
public:bool Getpath(TreeNode* root,TreeNode* x, stackTreeNode* path)
{if( root nullptr ) return false;path.push(root);if(root x)return true;if(Getpath(root-left,x,path))return true;if(Getpath(root-right,x,path))return true;path.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();}
};
最终结果思路二
首先刚开始从根节点开始遍历如果p和q中的任一个和root匹配那么root就是最低公共祖先。如果都不匹配此时我们分别去递归左、右子树如果有一个 节点出现在左子树并且另一个节点出现在右子树则root就是我们要找的值即最低公共祖先如果两个节点都出现在左子树则说明最低公共祖先在左子树中否则在右子树中。代码展示
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if( root nullptr ){return nullptr;}//如果p和q中的任一个和root匹配那么root就是最进公共祖先if( root p || root q ){return root;}//如果都不匹配则分别递归左、右子树TreeNode* left lowestCommonAncestor( root-left , p , q );TreeNode* right lowestCommonAncestor( root-right , p , q );//如果有一个节点出现在左子树并且另一个节点出现在右子树则root就是最低公共祖先.if( left ! nullptr right ! nullptr ){return root;} //如果两个节点都出现在左子树则说明最低公共祖先在左子树中否则在右子树if( right nullptr ){return left;} return right; }
};
最终结果到此便是本期题目的所有讲解内容了希望对大家有所帮助
