合肥网站建设方案书,国外不织布网站做的教具,体验营销理论,wordpress自动链接到图片大小第一题#xff1a;最大二叉树
题目描述#xff1a;654. 最大二叉树 - 力扣#xff08;LeetCode#xff09; 我的想法#xff1a;
我感觉这个题目最开始大家都能想到的暴力做法就是遍历找到数组中的最大值#xff0c;然后再遍历一遍#xff0c;把在它左边的依次找到最大…第一题最大二叉树
题目描述654. 最大二叉树 - 力扣LeetCode 我的想法
我感觉这个题目最开始大家都能想到的暴力做法就是遍历找到数组中的最大值然后再遍历一遍把在它左边的依次找到最大值但是emmm感觉效率很低时间上肯定过不了
然后其实我会觉得这个题目跟大根堆和小根堆有一点像就是先建立一个树来然后如果大就上去如果小就下来但是有一点怎么保证顺序因为这样先建立一棵树来再上移好像不能保证我浅浅画个图 那这样是让6之后的全部向上移动吗移动到6的右边
题目分析
嗯看了一圈好像没有人用小根堆大根堆写哈有用单调栈写的有用DFS写然后其实我那个初始想法版本也行因为我的题解给我的就是这样写的但是有一点不一样的是它分割了数组递归我就是憨憨的非要把每一步写出来哈其实每一个节点做的事情一样就一定一定抽象出来然后递归 就是相当于先找到数组中的最大值然后左右两边分别交给左右儿子再去做分割
其实这样我们可以总结一个思想就是
其实每一个节点都是首先把自己构造出来然后想办法构造自己的左右子树就相当于每一个人都有当孩子和当父亲的一天你要在孩子时期规定此时要做的事要在父亲时期规定要做的事然后每一个人的框架都是如此只不过最后做出来的成果可能不一样
我的错误题解
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {// 只要不断地传递就可以了天哪噜return build(nums, 0, nums.length - 1);}TreeNode build(int[] nums ,int lo,int hi){if(lohi)return null;int maxnums[lo];int indexlo;//找到数组中地最大值然后构建这个节点再分配左右儿子的数组for(int ilo1;ihi;i){if(nums[i]max){maxnums[i];indexi;}}//一般,数组传递下标,而不是非得要找到这个数是多少//创建这个节点TreeNode root new TreeNode(max);root.leftbuild(nums,lo,index-1);root.leftbuild(nums,index1,hi);return root;}
} 其实这个错误原因很好分析一看我去右边的好像都没进去所以直接检查代码发现root.right写错了写成了root.left
题解
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {// 只要不断地传递就可以了天哪噜return build(nums, 0, nums.length - 1);}TreeNode build(int[] nums ,int lo,int hi){if(lohi)return null;int maxnums[lo];int indexlo;//找到数组中地最大值然后构建这个节点再分配左右儿子的数组for(int ilo1;ihi;i){if(nums[i]max){maxnums[i];indexi;}}//一般,数组传递下标,而不是非得要找到这个数是多少//创建这个节点TreeNode root new TreeNode(max);root.leftbuild(nums,lo,index-1);root.rightbuild(nums,index1,hi);return root;}
}
这个题目想清楚了之后代码写起来和思维都不是很难的 第二题从前序与中序遍历序列构造二叉树
题目描述105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode 我的想法
soga这个用前序和中序构建树这个题目老师原来讲过挺经典的题的
而且无论是前序还是后序都必须要知道中序序列才有唯一的二叉树确定
应该思路是这样的
先从preorder里边开始最开始是3 然后在inorder里边找33就把inorder分成了两半左边是左子树里边的右边就是右子树里边的然后一直一直这样下去最后这棵树就建好了这里的思路有点小问题看到后面就知道了
我的题解
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {//1.建立头节点//拿到头节点在inorder中的位置然后分割左右//左边就是新的inorder 右边也是新的inorder//2.建立左右子节点//3.什么时候结束int index0;return build(index,preorder,inorder,0,inorder.length-1);}public static TreeNode build(int index,int[] preorder, int[] inorder,int lf,int lr){if(lflr)return null;int findplace0; TreeNode root new TreeNode(preorder[index-1]);index;for(int i0;iinorder.length;i){if(inorder[i]root.val){findplacei;break;}}//突然感觉index传的不对啊 这个index是互通的吗root.leftbuild(index,preorder,inorder,lf,findplace-1);root.rightbuild(index,preorder,inorder,findplace1,lr);return root;}
}
为啥越界了 题目分析 for循环遍历确定index效率不高可以考虑进一步优化
因为题目说二叉树结点的值不重复所以我们可以使用一个hashmap存储元素到索引的映射这样就可以直接通过hashMap查到rootVal对应的index 我天我知道了我的有一点的错误了
就是在preorder里边遍历其实是不需要一个一个遍历怎么说呢因为你一直把index传给左右两颗子树但是其实左右两颗子树里边需要的index并不相同因为它们的元素就不相同所以这样干没有考虑周到笑死我了根据下面这张图应该能很明显的看到preorder其实把它分成了这样两个部分 也就是说现在想指向某个值在数组里边对应的下标的时候可以不需要遍历直接用hashmap映射就可以了它的值就是它的下标
题解
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public static HashMapInteger,Integer valToIndex new HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {//1.建立头节点//拿到头节点在inorder中的位置然后分割左右//左边就是新的inorder 右边也是新的inorder//2.建立左右子节点//3.什么时候结束//HashMap优化for(int i0;ipreorder.length;i){valToIndex.put(inorder[i],i);}return build(0,preorder.length-1,preorder,inorder,0,inorder.length-1);}public static TreeNode build(int preFirst,int preLast,int[] preorder, int[] inorder,int lf,int lr){if(preFirstpreLast)return null;//分步完善 rootVal index leftSizeint rootVal preorder[preFirst];int indexvalToIndex.get(rootVal);int leftSizeindex-lf;//构造父结点TreeNode root new TreeNode(rootVal);/*有了hashmap这一步可以简化了for(int i0;iinorder.length;i){if(inorder[i]root.val){findplacei;break;}} */root.leftbuild(preFirst1 , preFirstleftSize , preorder , inorder , lf , index-1);root.rightbuild(preFirstleftSize1 , preLast , preorder , inorder , index1 , lr);return root;}
}
第三题根据前序和后序遍历构造二叉树
题目描述889. 根据前序和后序遍历构造二叉树 - 力扣LeetCode 我的想法
我没有想法惹惹惹我在想这两个题有啥区别
我的题解 题目分析
前两道题可以通过前序或者后序遍历找到根节点然后根据中序遍历结果确定左右子树
但这一道题可以确定根节点但是无法确切的知道左右子树有哪些节点
比如 但是解法还是和前两道题差别不大通过控制左右子树的索引来构建
1.首先把前序遍历结果的第一个元素或者后序遍历结果的最后一个元素作为根节点的值
2.然后把前序遍历结果的第二个元素作为左子树的根节点的值
3.在后序遍历结果中寻找左子树跟节点的值从而确定了左子树的索引边界进而确定右子树的索引边界然后递归构造左右子树即可
题解
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {//依然是下标到数的hash映射HashMapInteger,Integer valToIndex new HashMap();public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {for(int i0;ipostorder.length;i){valToIndex.put(postorder[i],i);}return build(preorder,0,preorder.length-1,postorder,0,postorder.length-1);}TreeNode build(int[] preorder,int preStart ,int preEnd,int[] postorder,int postStart,int postEnd){if(preStart preEnd)return null;if(preStartpreEnd)return new TreeNode(preorder[preStart]);//root节点对应的值就是前序遍历数组的第一个元素int rootVal preorder[preStart];//root.left 的值是前序遍历元素第二个元素//通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点//确定preorder 和postorder 中左右子树的元素区间int leftRootVal preorder[preStart1]; //leftRootVal 在后序遍历数组中的索引int index valToIndex.get(leftRootVal);//左子树的元素个数int leftSize index-postStart 1;//先构造出当前根节点TreeNode root new TreeNode(rootVal);//递归构造左右子树//根据左子树的根节点索引和元素个数推导左右子树的索引边界root.left build(preorder,preStart1,preStartleftSize,postorder,postStart,index);root.right build(preorder,preStartleftSize1,preEnd,postorder,index1,preEnd-1); //是因为左闭右开吗 //好像因为要用到两个preorder里边一次性用两个第一个为头节点第二个为左孩子节点return root;}
}
我要背题目阿巴
