代码随想录算法训练营第14天|654.最大二叉树，617.合并二叉树，700.二叉搜索树中的搜索，98.验证二叉搜索树

654. 最大二叉树看到题目的第一想法看来也是一个构建二叉树的题目只不过这个只需要一个数组其左右数组就是左右子树看完代码随想录的第一想法跟之前构建二叉树差不多这次就是找到最大值然后传入左右子树的开始和结束找左右子树的最大值用自己的话描述首先先定义我用的是左闭右开找到当前数组的最大数和他的下标根据下标找到这个数组左右子树的开始和末尾然后开始左右子树的递归将传回来的节点传入左子节点和右子节点然后返回当前的节点代码/** * 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; * } * } */classSolution{publicTreeNodeconstructMaximumBinaryTree(int[]nums){//递归三部曲//1.找到递归参数和返回值//2.找到递归的终止条件//3.找到递归的单层遍历是什么//递归参数是一个数组和数组的开始和结尾返回值为这个根节点//终止条件为数组的开始和结尾相等//单层递归先将该层根节点传入然后将该层的左右子树的开始和结尾算出来然后传入下一个递归将传回来的节点赋于左右子树returnMaxTreeNode(nums,0,nums.length);}publicTreeNodeMaxTreeNode(int[]nums,intnumsStart,intnumsEnd){if(numsStartnumsEnd){returnnull;}intmaxNumnums[numsStart];intindexnumsStart;for(intinumsStart;inumsEnd;i){if(nums[i]maxNum){maxNumnums[i];indexi;}}TreeNoderootnewTreeNode(maxNum);intleftnumsStartnumsStart;intleftnumsEndindex;intrightnumsStartindex1;intrightnumsEndnumsEnd;root.leftMaxTreeNode(nums,leftnumsStart,leftnumsEnd);root.rightMaxTreeNode(nums,rightnumsStart,rightnumsEnd);returnroot;}}实现过程中遇到哪些困难有了上一题的经验这一题没什么困难今日收获记录一下自己的学习时长继续熟练构造二叉树16.30-17.10617. 合并二叉树看到题目的第一想法其实就是根据两个二叉树构建一个新的二叉树看完代码随想录的第一想法就是改变了传入的参数从之前做过的传入数组变成传入两个树两颗树一起递归就是在一个递归中传两个树的参数用自己的话描述先找到该节点两个树的值然后将两个树的值相加组成一个新的树的值然后将两个树进入左子树的递归然后将返回来的节点传入新树的左子节点两个树进入右子树的递归然后将返回来的节点传入新树的右子节点返回这个节点值代码/** * 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; * } * } */classSolution{publicTreeNodemergeTrees(TreeNoderoot1,TreeNoderoot2){//递归三部曲//1.找到递归参数和返回值//2.找到递归的终止条件//3.找到递归的单层遍历是什么//1.递归参数为两颗树因为是需要两个树一起递归返回值树节点因为是构造一个树//2.递归终止条件为两个节点同时为null其中一个节点为null就返回另一个节点的值//3.先构建该树节点然后再构建左右子树的节点if(root1nullroot2null){returnnull;}if(root1null)returnroot2;if(root2null)returnroot1;intvalueroot1.valroot2.val;TreeNoderootnewTreeNode(value);root.leftmergeTrees(root1.left,root2.left);root.rightmergeTrees(root1.right,root2.right);returnroot;}}实现过程中遇到哪些困难无今日收获记录一下自己的学习时长继续熟悉递归的使用和构建二叉树21.35-21.54700. 二叉搜索树中的搜索看到题目的第一想法就是找子节点然后返回嘛应该很简单看完代码随想录的第一想法在结合找子节点的基础上加了二叉搜索树的特性进行查找用自己的话描述进入当前节点如果当前节点为null就返回当前节点如果当前节点的值当前搜索值返回当前节点如果都不是就判断搜索值大于当前节点的值还是小于小于将左子节点传入大于将右子节点传入然后返回他们两个其中递归的那一个返回代码/** * 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; * } * } */classSolution{publicTreeNodesearchBST(TreeNoderoot,intval){//递归三部曲//1.找到递归参数和返回值//2.找到递归的终止条件//3.找到递归的单层遍历是什么//1.递归参数就是传入当前节点和搜索值返回值就是一个树节点可以代表一个树//2.递归的终止条件要么是找不到节点了递归到当前节点为null返回null要么就是找到子节点了返回子节点//3.就是先判断当前节点是不是null如果是直接返回如果找到值了就返回节点//然后开始对判断当前值是大当前节点还是小于当前节点决定进入左子树还是右子树//返回左子树或右子树的节点if(rootnull||root.valval){returnroot;}TreeNoderesnull;if(root.valval){ressearchBST(root.right,val);}else{ressearchBST(root.left,val);}returnres;}}实现过程中遇到哪些困难无今日收获记录一下自己的学习时长了解了二叉搜索树的定义和其运用21.55-22.2198. 验证二叉搜索树看到题目的第一想法验证二叉搜索树这个题目确实是一点思路都没有看完代码随想录的第一想法一个是先通过递归把二叉搜索树都放到一个数组中然后对进行遍历看看是不是从小到大进行但是还有另一个思路就是一边递归一边比较大小然后如果比较不成功就false用自己的话描述进入节点递归先判断是否为空节点不为空节点就继续进入左子树递归直到找到空节点返回true然后进入最左边的叶子节点判断他的值是不是大于最大值大于就进入右子树递归返回true然后判断该节点是否为二叉搜索树true代码/** * 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; * } * } */classSolution{longmaxLong.MIN_VALUE;publicbooleanisValidBST(TreeNoderoot){//递归三部曲//1.找到递归参数和返回值//2.找到递归的终止条件//3.找到递归的单层遍历是什么//1.传一个根节点进去判断这个是不是二叉搜索树所以要返回true或false//2.递归终止条件是当递归到空节点的时候再返回true证明这是二叉搜索树//3.先判断终止条件然后进入左子节点递归然后判断该节点的值是否大于最大值大于就返回继续进入右子节点递归//否则就返回falseif(rootnull){returntrue;}booleanleftisValidBST(root.left);if(root.valmax){returnfalse;}maxroot.val;booleanrightisValidBST(root.right);returnleftright;}}实现过程中遇到哪些困难递归的验证还是有点难想的今日收获记录一下自己的学习时长对于加入一个最大值就能判断这个树的顺序让我更加明白了树的递归顺序22.22-23.10