小城镇建设网站,织梦cms发布侵权网站清单,wordpress网站搬家vps,网站备案转移对于二叉树#xff0c;很难#xff0c;很难#xff01;笔者也是感觉很难#xff01;虽然能听懂课程#xff0c;但是#xff0c;对于大部分的练习题并不能做出来#xff01;所以感觉很尴尬#xff01;#xff01;因此#xff0c;笔者经过先前的那篇博客#xff0c;已…对于二叉树很难很难笔者也是感觉很难虽然能听懂课程但是对于大部分的练习题并不能做出来所以感觉很尴尬因此笔者经过先前的那篇博客已经开启了大脑奇迹现在还热乎着刚刚的更文二叉树讲解https://blog.csdn.net/weixin_64308540/article/details/129046267?spm1001.2014.3001.5501言归正传这篇文章主要在于二叉树的相关列题大概也就十来个但是基本每个都有代码思路还有一些瞎扯白那就确实不容易了100. 相同的树给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。 示例 1输入p [1,2,3], q [1,2,3]输出true示例 2输入p [1,2], q [1,null,2]输出false示例 3输入p [1,2,1], q [1,1,2]输出false 提示两棵树上的节点数目都在范围 [0, 100] 内-104 Node.val 104根据上述的题目我们可以得出如果根节点相同则判断左节点是否相同继而判断右节点是否相同那么何为相同呢对于相同不相同我们有着一下的感想结构为空不为空1一个为空一个不为空2两个都为空32个都不为空不一定还得看val值值val)根据上述的思考我们可以有着下述的简单代码 //判断两个树是否相同public boolean isSameTree(TreeNode p,TreeNode q){if (pnull q !null || p !null qnull){return false;}//此时p,q 要不都是空要不都不是空if (pnull qnull){return true;//都为空树此时也相同}if (p.val !q.val){return false;//都不是空且值不相同的情况下}//此时p,q都不是空且根节点一样那么继续判断左子树/右子树return isSameTree(p.left,q.left) isSameTree(p.right,q.right);}这个代码看着很简单但是写起来容易缺少思路感兴趣的可以思考一下时间复杂度与空间复杂度572. 另一棵树的子树给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。 示例 1输入root [3,4,5,1,2], subRoot [4,1,2]输出true示例 2输入root [3,4,5,1,2,null,null,null,null,0], subRoot [4,1,2]输出false 提示root 树上的节点数量范围是 [1, 2000]subRoot 树上的节点数量范围是 [1, 1000]-104 root.val 104-104 subRoot.val 104根据上述题目的案列我们可以得出思路是不是相同的树是不是root的左子树是不是root的右子树那么我们可以有着下述的代码 //判断两个树是否相同public boolean isSameTree(TreeNode p,TreeNode q){if (pnull q !null || p !null qnull){return false;}//此时p,q 要不都是空要不都不是空if (pnull qnull){return true;//都为空树此时也相同}if (p.val !q.val){return false;//都不是空且值不相同的情况下}//此时p,q都不是空且根节点一样那么继续判断左子树/右子树return isSameTree(p.left,q.left) isSameTree(p.right,q.right);}//另一颗子树public boolean isSubTree(TreeNode root,TreeNode subRot){if (rootnull ||subRotnull){return false;}if (isSameTree(root,subRot)){return true;}if (isSameTree(root.left,subRot)){return true;}if (isSameTree(root.right,subRot)){return true;}return false;}该段代码我们借助是不是相同的树的代码了显得我们有点儿投机取巧了感兴趣的读者可以思考一下时间复杂度与空间复杂度226. 翻转二叉树给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 示例 1输入root [4,2,7,1,3,6,9]输出[4,7,2,9,6,3,1]示例 2输入root [2,1,3]输出[2,3,1]示例 3输入root []输出[] 提示树中节点数目范围在 [0, 100] 内-100 Node.val 100对于实列中的代码我们可以看出最后得出root的左子树和root的右子树实现了交换交换的是左右两个子树而不是仅仅交换哪个节点参考代码 //翻转二叉树public TreeNode invertTree(TreeNode root){if (rootnull){return null;}TreeNode tmproot.left;root.leftroot.right;root.righttmp;invertTree(root.left);invertTree(root.right);return root;}110. 平衡二叉树给定一个二叉树判断它是否是高度平衡的二叉树。本题中一棵高度平衡二叉树定义为一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1输入root [3,9,20,null,null,15,7]输出true示例 2输入root [1,2,2,3,3,null,null,4,4]输出false示例 3输入root []输出true 提示树中的节点数在范围 [0, 5000] 内-104 Node.val 104对于该题目我们可以看出左右高度差不超过1每个节点都要求高度写法1 //平衡二叉树public boolean isBalanced(TreeNode root){if (rootnull){return true;}int leftHmaxDepth(root.left);int rightHmaxDepth(root.right);return Math.abs(leftH-rightH)2 isBalanced(root.left)isBalanced(root.right);}//求树的高度public int maxDepth(TreeNode root){if (rootnull){return 0;}int leftHeightmaxDepth(root.left);int rightHeightmaxDepth(root.right);return (leftHeight rightHeight) ? (leftHeight1) : (rightHeight1);}对于这个题目我们会是感觉很难很难而且时间复杂度很大很大在力扣上面直接跑不过超时该时间复杂度为O(n^2)那么我们是否可以写一个时间复杂度为O(n)的呢请看下述的代码写法2在求高度的过程中判断是不是平衡二叉树 public boolean isBalanced2(TreeNode root){return maxDepth2(root)0;}public int maxDepth2(TreeNode root){if (rootnull){return 0;}int leftHeightmaxDepth2(root.left);int rightHeightmaxDepth2(root.right);if (leftHeight0 rightHeight0 Math.abs(leftHeight-rightHeight)1){return Math.max(leftHeight,rightHeight)1;//求最大值}else {return -1;//不平衡返回一个负数}}101. 对称二叉树给你一个二叉树的根节点 root 检查它是否轴对称。 示例 1输入root [1,2,2,3,4,4,3]输出true示例 2输入root [1,2,2,null,3,null,3]输出false 提示树中节点数目在范围 [1, 1000] 内-100 Node.val 100根据题意我们可以看出判断这棵树是不是轴对称的主要在于判断这棵树的左子树和这棵树的右子树是否对称判断方法判断左子树的左树和右子树的右树 判断左子树的右树和右子树的左树参考代码为 //对称二叉树public boolean isSymmetric(TreeNode root){if (rootnull){return true;//判断根节点是否为空}return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){if (leftTree ! null rightTreenull || leftTreenull rightTree !null){return false;//一个为空一个不为空}if (leftTreenull rightTreenull){return true;//两个都为空}if (leftTree.val ! rightTree.val){return false;}//判断左子树的左树和右子树的右树//判断左子树的右树和右子树的左树return isSymmetricChild(leftTree.left,rightTree.right)isSymmetricChild(leftTree.right,rightTree.left);}102. 二叉树的层序遍历给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 示例 1输入root [3,9,20,null,null,15,7]输出[[3],[9,20],[15,7]]示例 2输入root [1]输出[[1]]示例 3输入root []输出[] 提示树中节点数目在范围 [0, 2000] 内-1000 Node.val 1000对于这个题目我们可以考虑用队列队列的先进先出模式符合一层层遍历的逻辑写法1 //二叉树的层序遍历public void levelOrder(TreeNode root){if (rootnull){return;}//队列QueueTreeNode queuenew LinkedList();queue.offer(root);//先把根节点放在队列里while ( !queue.isEmpty()){//当前队列不为空TreeNode curqueue.poll();//弹出出队列System.out.print(cur.val );if (cur.left !null){queue.offer(cur.left);//入队列}if (cur.right !null){queue.offer(cur.right);}}}写法2 public ListListInteger levelOrder2(TreeNode root){ListListInteger listnew ArrayList();if (rootnull){return list;}QueueTreeNode queuenew LinkedList();queue.offer(root);while ( !queue.isEmpty()){int sizequeue.size();ListInteger tmpnew ArrayList();while (size!0){TreeNode curqueue.poll();size--;if (cur.left !null){queue.offer(cur.left);}if (cur.right !null){queue.offer(cur.right);}}list.add(tmp);}return list;}对于写法2 其实还是使用了二维数组二维数组对于这个写法其实我在之前的杨辉三家中有过具体的描述若是不懂得各位老铁可以翻一下笔者之前的博客或者来咨询一下笔者KY11 二叉树遍历描述编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。输入描述输入包括1行字符串长度不超过100。输出描述可能有多组测试数据对于每组数据 输出将输入字符串建立二叉树后中序遍历的序列每个字符后面都有一个空格。 每个输出结果占一行。示例1输入abc##de#g##f###复制输出c b e g d f a 根据题目的这个案列我们可以创建一棵二叉树那么我们可以有着一下所示的代码import java.util.Scanner;public class TreeNode {public char val;public TreeNode left;public TreeNode right;//构造方法public TreeNode(char val) {this.val val;}public static void main(String[] args) {Scanner in new Scanner(System.in);while (in.hasNextLine()){String strin.nextLine();//定义root接收这个树的节点TreeNode rootcreatrTree(str);inorder(root);//中序遍历}}public static int i0;//i不会越界有递归次数的限制public static TreeNode creatrTree(String str){TreeNode rootnull;if (str.charAt(i) ! #){//根左右rootnew TreeNode(str.charAt(i));i;root.leftcreatrTree(str);//左数root.rightcreatrTree(str);//右数}else {i;}return root;}//中序遍历public static void inorder(TreeNode root){if (rootnull){return;}inorder(root.left);//左System.out.print(root.val );//根inorder(root.right);//右}
}
236. 二叉树的最近公共祖先给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 示例 1输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1
输出3
解释节点 5 和节点 1 的最近公共祖先是节点 3 。示例 2输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4
输出5
解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3输入root [1,2], p 1, q 2输出1 提示树中节点数目在范围 [2, 105] 内。-109 Node.val 109所有 Node.val 互不相同 。p ! qp 和 q 均存在于给定的二叉树中。对于上述的题目我们可以得出一下思考因此要么在根的左右两边要么在根的左边或者右边要么在根的左边或者右边其中一个节点是公共祖先那么我们可以有着一下 的代码 //二叉树的最近公共祖先public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){if (rootnull){return null;}//先判断根节点是否为其中一个if (rootp || rootq){return root;}//左边找找TreeNode leftRetlowestCommonAncestor(root.left,p,q);//右边找找TreeNode rightRetlowestCommonAncestor(root.right,p,q);if (leftRet!null rightRet !null){return root;//左右两边都找到了}else if (leftRet!null){return leftRet;//左边找到了}else if (rightRet!null){return rightRet;//右边找到了}return null;}105. 从前序与中序遍历序列构造二叉树给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 示例 1:输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7]输出: [3,9,20,null,null,15,7]示例 2:输入: preorder [-1], inorder [-1]输出: [-1] 提示:1 preorder.length 3000inorder.length preorder.length-3000 preorder[i], inorder[i] 3000preorder 和 inorder 均 无重复 元素inorder 均出现在 preorderpreorder 保证 为二叉树的前序遍历序列inorder 保证 为二叉树的中序遍历序列首先我们需要知道的是前序遍历的第一个节点是根节点中序遍历找到根节点左侧的是左树右侧的是右树那么我们可以有着下述的简单代码//从前序遍历与中序遍历构造二叉树
public class Solution {class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}public TreeNode(int val) {this.val val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}}int i0;public TreeNode buildTree(int[] preorder , int[] inorder){return buildTreeChild(preorder,inorder,0,inorder.length-1);}//preorder前序遍历//inorder中序遍历public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){if (inbegin inend){return null;//没有子树}TreeNode root new TreeNode(preorder[i]);int rootIndexfindIndex(inorder,inbegin,inend,preorder[i]);i;root.leftbuildTreeChild(preorder,inorder,inbegin,rootIndex-1);root.rightbuildTreeChild(preorder,inorder,rootIndex1,inend);return root;}private int findIndex(int[] inorder,int inbegin,int inend,int key){for (int i 0; i inend; i) {if (inorder[i]key){return i;}}return -1;}
}代码有点儿复杂大家自求多福106. 从中序与后序遍历序列构造二叉树给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 示例 1:输入inorder [9,3,15,20,7], postorder [9,15,7,20,3]输出[3,9,20,null,null,15,7]示例 2:输入inorder [-1], postorder [-1]输出[-1] 提示:1 inorder.length 3000postorder.length inorder.length-3000 inorder[i], postorder[i] 3000inorder 和 postorder 都由 不同 的值组成postorder 中每一个值都在 inorder 中inorder 保证是树的中序遍历postorder 保证是树的后序遍历//从中序与后序遍历序列构造二叉树
public class Test1 {class TreeNode{int val;Solution.TreeNode left;Solution.TreeNode right;TreeNode(){}public TreeNode(int val) {this.val val;}public TreeNode(int val, Solution.TreeNode left, Solution.TreeNode right) {this.val val;this.left left;this.right right;}}int i0;public TreeNode buildTree(int[] inorder,int[] postorder){int ipostorder.length-1;return buildTreeChild2(postorder,inorder,0,inorder.length-1);}public TreeNode buildTreeChild2(int[] postorder,int[] inorder,int inbegin,int inend){if (inbegininend){return null;}TreeNode rootnew TreeNode(postorder[i]);//找到当前根在中序遍历的位置int rootIndexfindIndex(inorder,inbegin,inend,postorder[i]);i--;root.rightbuildTreeChild2(postorder,inorder,rootIndex1,inend);root.leftbuildTreeChild2(postorder,inorder,inbegin,rootIndex-1);return root;}private int findIndex(int[] inorder,int inbegin,int inend,int key){for (int i 0; i inend; i) {if (inorder[i]key){return i;}}return -1;}
}
606. 根据二叉树创建字符串给你二叉树的根节点 root 请你采用前序遍历的方式将二叉树转化为一个由括号和整数组成的字符串返回构造出的字符串。空节点使用一对空括号对 () 表示转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。 示例 1输入root [1,2,3,4]输出1(2(4))(3)解释初步转化后得到 1(2(4)())(3()()) 但省略所有不必要的空括号对后字符串应该是1(2(4))(3) 。示例 2输入root [1,2,3,null,4]输出1(2()(4))(3)解释和第一个示例类似但是无法省略第一个空括号对否则会破坏输入与输出一一映射的关系。 提示树中节点的数目范围是 [1, 104]-1000 Node.val 1000对于该题目我们可以左边为空右边也为空左边不为空右边为空左边为空右边不为空那么请看笔者的代码 //根据二叉树创建字符串public String tree2Str(TreeNode root){if (rootnull){return null;}//为拼接做准备StringBuilder stringBuilder new StringBuilder();tree2StrChild(root,stringBuilder);return stringBuilder.toString();//类型转化}//拼接不能用进行拼接public void tree2StrChild(TreeNode t,StringBuilder stringBulider){if (tnull){return;}stringBulider.append(t.val);//拼接根if (t.left!null){//左边不为空加“”再递归这颗左树stringBulider.append(();tree2StrChild(t.left,stringBulider);stringBulider.append());//当t.left走完了回去的时候加)}else {//左边空了if (t.right!null){stringBulider.append(());}else {//右边为空return;//左边为空右边也为空}}if (t.rightnull){//右边为空return;}else {//右边不为空stringBulider.append(();tree2StrChild(t.right,stringBulider);//递归右数stringBulider.append());}}判断一棵树是不是完全二叉树完全二叉树一颗深读为K的有n个节点的二叉树对树中的节点按从上到下从左到右的顺序进行编写如果编号为i(1in)的节点与满二叉树中编号为i的节点在二叉树中的位置相同那么这颗二叉树称为完全二叉树//判断一棵树是不是完全二叉树boolean isCompleteTree(TreeNode root){if (rootnull){return true;}//借助队列类似于层序遍历去做QueueTreeNode queuenew LinkedList();queue.offer(root);while (!queue.isEmpty()){//队列不为空TreeNode curqueue.poll();//出栈if (cur!null){queue.offer(cur.left);//入栈queue.offer(cur.right);}else {break;//遇到了null跳出该循环}}while (!queue.isEmpty()){TreeNode tmpqueue.poll();if (tmp!null){return false;}}return true;}二叉树的相关列题便就这么多吧但是当你全部理解的时候二叉树的知识已经难不倒你了
