第六章 二叉树 part05
详细布置
654.最大二叉树
又是构造二叉树,昨天大家刚刚做完 中序后序确定二叉树,今天做这个 应该会容易一些, 先看视频,好好体会一下 为什么构造二叉树都是 前序遍历
题目链接/文章讲解:https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html
视频讲解:https://www.bilibili.com/video/BV1MG411G7ox
617.合并二叉树
这次是一起操作两个二叉树了, 估计大家也没一起操作过两个二叉树,也不知道该如何一起操作,可以看视频先理解一下。 优先掌握递归。
题目链接/文章讲解:https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html
视频讲解:https://www.bilibili.com/video/BV1m14y1Y7JK
700.二叉搜索树中的搜索
递归和迭代 都可以掌握以下,因为本题比较简单, 了解一下 二叉搜索树的特性
题目链接/文章讲解: https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html
视频讲解:https://www.bilibili.com/video/BV1wG411g7sF
98.验证二叉搜索树
遇到 搜索树,一定想着中序遍历,这样才能利用上特性。
但本题是有陷阱的,可以自己先做一做,然后在看题解,看看自己是不是掉陷阱里了。这样理解的更深刻。
题目链接/文章讲解:https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
视频讲解:https://www.bilibili.com/video/BV18P411n7Q4
654.最大二叉树
题目链接
https://leetcode.cn/problems/maximum-binary-tree/description/
解题思路
分析题目即可解出代码,
开始每次都重建了数组,优化后的代码一直复用同一个数组,递归函数加入子数组的范围下标即可。
code
public TreeNode constructMaximumBinaryTree(int[] nums) {
return recursion(nums,0,nums.length-1);
}
//复用一个数组,根据索引下标切割子数组
public TreeNode recursion(int[] nums,int left,int right){
if(nums.length==0||left>right){
return null;
}
//找到最大值作为根节点
int index=0;
int maxValue=Integer.MIN_VALUE;
for(int i=left;i<=right;i++){
if(nums[i]>maxValue){
maxValue=nums[i];
index=i;
}
}
TreeNode root=new TreeNode(maxValue);
root.left=recursion(nums,left,index-1);
root.right=recursion(nums,index+1,right);
return root;
}
//每次重建数组
public TreeNode constructMaximumBinaryTree2(int[] nums) {
if(nums.length==0){
return null;
}
//找到最大值作为根节点
int index=0;
int maxValue=Integer.MIN_VALUE;
for(int i=0;i<nums.length;i++){
if(nums[i]>maxValue){
maxValue=nums[i];
index=i;
}
}
TreeNode root=new TreeNode(maxValue);
int[] leftNums=new int[index];
System.arraycopy(nums,0,leftNums,0,leftNums.length);
int[] rightNums=new int[nums.length-1-leftNums.length];
System.arraycopy(nums,leftNums.length+1,rightNums,0,rightNums.length);
root.left=constructMaximumBinaryTree(leftNums);
root.right=constructMaximumBinaryTree(rightNums);
return root;
}
617.合并二叉树
题目链接
https://leetcode.cn/problems/merge-two-binary-trees/description/
解题思路
使用前序遍历合并
递归终止条件就是 俩颗树遍历都为null了,其中一个为null返回另一个都不需要继续向下递归了。
中条件就是 俩颗树的值相加,生成一个新节点,这个新节点可以复用root1的树,在root1这棵树上变化。
code
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
//1.递归终止条件,都为null 都遇到了空节点返回null
if(root1==null&&root2==null){
return null;
}
//root1是null 子树就是root2了不需要在递归了
if(root1==null){
return root2;
}
//root2是null 子树就是root1了不需要在递归了
if(root2==null){
return root1;
}
//TreeNode root=new TreeNode(root1.val+root2.val);//中
//复用root1的树
root1.val+=root2.val;
root1.left=mergeTrees(root1.left,root2.left);//左
root1.right=mergeTrees(root1.right,root2.right);//右
return root1;
700.二叉搜索树中的搜索
题目链接
解题思路
二叉搜索树的概念:
若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
它的左、右子树也分别为二叉搜索树
解题注意点:
不要忘了 递归函数还有返回值。
递归函数的返回值是什么? 是 左子树如果搜索到了val,要将该节点返回。 如果不用一个变量将其接住,那么返回值不就没了。
所以要res = searchBST(root->left, val)
最后返回res
code
public TreeNode searchBST(TreeNode root, int val) {
//节点为null 没找到
if(root==null){
return root;
}
//找到节点返回
if(root.val==val){
return root;
}
//记录递归结果 返回
TreeNode res=null;
if(root.val>val){
res=searchBST(root.left,val);
}else if(root.val<val){
res=searchBST(root.right,val);
}
return res;
}
98.验证二叉搜索树
题目链接
https://leetcode.cn/problems/validate-binary-search-tree/description/
解题思路
二叉搜索树 中序遍历单调递增,根据这个特性解题
定义前一个节点的指针,如果前一个节点大于等于当前节点,则不符合单调递增,则不是二叉搜索树
code
//二叉搜索树 中序遍历单调递增
public boolean isValidBST(TreeNode root) {
if(root==null){
return true;
}
boolean left=isValidBST(root.left);
if(pre!=null && pre.val>=root.val){
return false;
}else{
pre=root;
}
boolean right=isValidBST(root.right);
return left&&right;
}