2024年7月19日
题654. 最大二叉树
熟练运用递归即可
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
int maxNum = Integer.MIN_VALUE;
int flag=-1;
for(int i=0;i<nums.length;i++){
if(nums[i]>maxNum){
maxNum = nums[i];
flag=i;
}
}
int i=0,j=nums.length-1;
//此时被分为了[i,flag-1]和[flag+1,j]
TreeNode root = new TreeNode(nums[flag]);
root.left=digui(nums,i,flag-1);
root.right=digui(nums,flag+1,j);
return root;
}
public TreeNode digui(int[] nums,int left,int right){
//首先构建左子树的头,然后构建右子树的头
if(left>right){
return null;
}
//找出最大值
int maxNum = Integer.MIN_VALUE;
int flag=-1;
for(int i=left;i<=right;i++){
if(nums[i]>maxNum){
maxNum = nums[i];
flag=i;
}
}
int i=left,j=right;
TreeNode p = new TreeNode(nums[flag]);
p.left=digui(nums,i,flag-1);
p.right=digui(nums,flag+1,j);
return p;
}
}
题617. 合并二叉树
注意递归使用
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null && root2==null){
return null;
}else if(root1==null && root2!=null){
TreeNode root = new TreeNode(root2.val);
root.left = mergeTrees(null,root2.left);
root.right=mergeTrees(null,root2.right);
return root;
}else if(root1!=null && root2==null){
TreeNode root = new TreeNode(root1.val);
root.left = mergeTrees(null,root1.left);
root.right=mergeTrees(null,root1.right);
return root;
}else{
TreeNode root = new TreeNode(root1.val+root2.val);
root.left = mergeTrees(root2.left,root1.left);
root.right=mergeTrees(root2.right,root1.right);
return root;
}
}
}
题700. 二叉搜索树中的搜索
借助搜索树的特性剪枝,左子树更小,右子树更大
class Solution {
TreeNode p;
public TreeNode searchBST(TreeNode root, int val) {
p=null;
digui(root,val);
return p;
}
public void digui(TreeNode root,int val){
if(root==null){
return;
}else{
if(root.val==val){
p=root;
return;
}else{
if(root.val>val){
digui(root.left,val);
}else{
digui(root.right,val);
}
}
}
}
}
题98. 验证二叉搜索树
要想到中序遍历就是递增的,所以先得到中序然后检查是不是严格递增即可
import java.util.*;
class Solution {
Vector<Integer> vec;
public boolean isValidBST(TreeNode root) {
if(root==null){
return false;
}
vec = new Vector<>();
//中序遍历,然后检查是不是递增的
digui(root.left);
vec.add(root.val);
digui(root.right);
//检查vec
for(int i=0;i<vec.size()-1;i++){
if(vec.get(i)>=vec.get(i+1)){
return false;
}
}
return true;
}
public void digui(TreeNode root){
if(root==null){
return;
}else{
digui(root.left);
vec.add(root.val);
digui(root.right);
}
}
}
标签:right,TreeNode,val,17,随想录,二叉,null,root,left
From: https://www.cnblogs.com/hailicy/p/18316260