代码随想录算法训练营第17天

654.最大二叉树

题目链接：654. 最大二叉树 - 力扣（LeetCode）

视频链接：又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树_哔哩哔哩_bilibili

代码随想录

构造二叉树选用前序遍历，中左右

参数：nums数组，左右下标。返回值：node

终止条件：数组大小为0，返回null；数组大小为1，返回根结点

中间结点逻辑：找到最大值

左边：首先必须要保证有一个元素即index>0,新数组左闭右开分割区间

右边：必须要保证一个元素index<nums.size()-1,新数组左闭右开分割区间。

优化：构造新数组优化为传入左右下标参数

写不写if关键在于终止条件，我们的终止条件是数组大小为1，所以if要保证有一个元素。

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return BuildMaxBinaryTree(nums,0,nums.length);}public TreeNode BuildMaxBinaryTree(int[] nums,int leftIndex,int rightIndex){if(rightIndex-leftIndex<1){return null;//没有元素}//终止条件if(rightIndex-leftIndex==1){return new TreeNode(nums[leftIndex]);//此时[leftIndex,rightIndex)}//中间结点处理逻辑int max = Integer.MIN_VALUE;int index = leftIndex;for (int i = leftIndex; i < rightIndex; i++) {if(nums[i]>max){max = nums[i];index = i;}}TreeNode curNode = new TreeNode(nums[index]);//左边结点,保证左边至少有一个结点if(index-leftIndex>0){curNode.left = BuildMaxBinaryTree(nums,leftIndex,index);}if(rightIndex-index>1){curNode.right = BuildMaxBinaryTree(nums,index+1,rightIndex);}return curNode;}
}

617.合并二叉树

题目链接/文章讲解：代码随想录

视频讲解：一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树_哔哩哔哩_bilibili

第一想法

返回值：叶子结点。传入参数：两棵树的当前结点结点

遍历方式：中左右，前序遍历

代码

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {//终止条件if(root1!=null&&root2==null)return root1;if(root1==null&&root2!=null)return root2;if(root1==null&&root2==null)return null;//当前结点TreeNode curNode = new TreeNode(root1.val + root2.val);//左结点处理curNode.left = mergeTrees(root1.left,root2.left);//右结点处理curNode.right = mergeTrees(root1.right,root2.right);return curNode;}
}

代码优化

不要新造树，在root1树上叠加root2

class Solution {// 递归public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 == null) return root2;if (root2 == null) return root1;root1.val += root2.val;root1.left = mergeTrees(root1.left,root2.left);root1.right = mergeTrees(root1.right,root2.right);return root1;}
}

700.二叉搜索树

题目链接/文章讲解: 代码随想录

视频讲解：不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索_哔哩哔哩_bilibili

第一想法

终止条件：当前结点为空，则返回空

处理当前结点：如果值相等，直接返回结点

否则遍历左右结点:如果遍历左结点返回值不为空，则返回左节点；如果遍历右结点返回值不为空，则返回右结点。

最终返回空

但是实践错误，代码超时

代码随想录

此题是二叉搜索树

二叉搜索树是一个有序树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树

并且我在初次尝试也习惯写searchBST（root.left,val)。这里代码随想录有这样解释：

很多录友写递归函数的时候习惯直接写 searchBST(root->left, val)，却忘了递归函数还有返回值。

递归函数的返回值是什么? 是左子树如果搜索到了val，要将该节点返回。如果不用一个变量将其接住，那么返回值不就没了。

所以要 result = searchBST(root->left, val)。

有没有变量接住返回值是要看函数返回值。

像这种遍历左和遍历右都有可能有返回值，应该用一个变量接住，而不是直接返回比如这种代码。

      if (searchBST(root.left,val)!=null) {return searchBST(root.left,val);}if(searchBST(root.right,val)!=null){return searchBST(root.right,val);}return null;

亦或者是这种：

        return searchBST(root.left,val);//遍历左边return searchBST(root.right,val);//遍历右边return null;//找不到则最终返回空

正确写法：

        //当向左向右遍历时TreeNode result = null;if(root.val>val) result = searchBST(root.left,val);if (root.val<val)result = searchBST(root.right,val);return result;

同时终止条件代码优化：

当前结点为空时返回当前结点，当前结点值满足某一条件时直接返回此结点。

        //终止条件if(root==null)return null;//当前结点if(root.val==val)return root;//终止条件可优化为此一句if(root==null||root.val==val)return root;

代码

class Solution {public TreeNode searchBST(TreeNode root, int val) {//终止条件可优化为此一句if(root==null||root.val==val)return root;//当向左向右遍历时TreeNode result = null;if(root.val>val) result = searchBST(root.left,val);if (root.val<val)result = searchBST(root.right,val);return result;}
}

98.验证二叉搜索树

题目链接/文章讲解：代码随想录

视频讲解：你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树_哔哩哔哩_bilibili

代码随想录

此题1个误区在于：粗暴的判断中结点大于左节点并且小于右结点，就符合二叉搜索树特点。

if(root.val>root.left.val&&root.val<root.right.val)return true;

但实际上二叉搜索树是要求中结点大于左子树的所有结点，小于右子树的所有节点。

此题属于二叉搜索树，要利用其中序遍历是递增数组的特点。

所以：

1. 要么选用全局变量记录当前已找到的最大值，按照中序遍历即左中右的顺序，只要中结点大于此最大值即可返回true，再更新最大值。

最大值的初始值一定要比第一个遍历的结点小。

2. 要么效仿检验数组是否递增设置同时移动的双指针：设置前置指针pre，只要当前值大于pre的值即可，并且更新pre。

pre初始化为null，因此在遍历第一个结点时，当pre为null时不能进入判断条件。

最后返回left&&right时根据左中右的遍历顺序实际上已经判断了中间节点（此点看视频）。

代码

class Solution {TreeNode pre = null;public boolean isValidBST(TreeNode root) {if(root==null)return true;boolean left = isValidBST(root.left);if(pre!=null&&pre.val>=root.val)return false;pre = root;boolean right = isValidBST(root.right);return left&&right;}
}