代码随想录算法刷题训练营day20：LeetCode(654)最大二叉树、LeetCode(617)合并二叉树、LeetCode(700)二叉搜索树中的搜索、LeetCode(700)二叉搜索树中的搜索、LeetCode(98)验证二叉搜索
LeetCode(654)最大二叉树
题目
代码
import java.util.Arrays;
/**
* 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) {
//递归----判断终止条件
if(nums.length==0){
return null;
}
int data[]=getMaxIndexAndValue(nums);
int dataIndex=data[0];
int dataValue=data[1];
TreeNode root=new TreeNode(dataValue);
//拆分数组
int[] leftNums=Arrays.copyOfRange(nums, 0, dataIndex);
int[] rightNums=Arrays.copyOfRange(nums, dataIndex+1, nums.length);
root.left=constructMaximumBinaryTree(leftNums);//左边构建左子树
root.right=constructMaximumBinaryTree(rightNums);//右边构建右子树
return root;
}
//定义一个函数用于获取数组中的最大值和对应的数组下标
public int[] getMaxIndexAndValue(int[] nums){
int[] result=new int[2];
int index=0;
int sum=0;
for (int i = 0; i < nums.length; i++) {
if(nums[i]>sum){
sum=nums[i];
index=i;
}
}
result[0]=index;
result[1]=sum;//记住最大值的下标和对应的值
return result;
}
}
LeetCode(617)合并二叉树
题目
代码
/**
* 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 mergeTrees(TreeNode root1, TreeNode root2) {
//先处理边角条件
if(root1==null&&root2==null){
return null;
}
if(root1==null&&root2!=null){
return root2;
}
if(root1!=null&&root2==null){
return root1;
}
TreeNode root=getMergeTrees(root1,root2);
return root;
}
//单独构建一个函数用于处理
public TreeNode getMergeTrees(TreeNode root1,TreeNode root2){
//终止条件
if(root1==null&&root2==null){
return null;
}
/* if(root1==null){
return root2;//树1为空即返回树2
}
if(root2==null){
return root1;
} */
TreeNode root=new TreeNode();
if(root1!=null&&root2==null){
/* root.val=root1.val;
return root; *///还会往下面走，所以空指针异常
/* root.val=root1.val; */
return root1;//树二已经没有了，需要把树1所有子树全部返回
//
}
if(root1==null&&root2!=null){
/* root.val=root2.val;
return root; */
return root2;
}
//先序遍历----同时遍历到同一位置
if(root1!=null&&root2!=null){
int data=root1.val+root2.val;
root.val=data;
}
//左子树遍历
root.left=getMergeTrees(root1.left, root2.left);
//右子树遍历
root.right=getMergeTrees(root1.right, root2.right);
return root;
}
}
LeetCode(700)二叉搜索树中的搜索
题目
代码
/**
* 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 searchBST(TreeNode root, int val) {
//递归----判断终止条件
if(root==null){
return null;
}
//前序遍历
if(root.val==val){
return root;
}
TreeNode result=new TreeNode();
//左边
//左子树
//二叉搜索树
//左边小于中间，右边大于中间
if(val<root.val){
//往左边走
result=searchBST(root.left, val);
}
if(val>root.val){
//右子树
result=searchBST(root.right, val);
}
return result;
}
}
LeetCode(98)验证二叉搜索
题目
代码
import java.util.ArrayList;
import java.util.List;
/**
* 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 boolean isValidBST(TreeNode root) {
//定义一个集合，遍历树存储到集合里面
//按中序遍历存储数据，若是二叉搜索树，则是一个升序数组
List<Integer> dateTree=new ArrayList<>();
getDateTree(root,dateTree);
for (int i = 0; i < dateTree.size()-1; i++) {
if(dateTree.get(i)>=dateTree.get(i+1)){
return false;
}
}
return true;
}
public void getDateTree(TreeNode root,List<Integer> dateTree){
if(root==null){
return;
}
getDateTree(root.left, dateTree);//左子树
dateTree.add(root.val);
getDateTree(root.right, dateTree);//右子树
}
}
