首页 > 编程语言 >代码随想录算法训练营第17天 | 复习二叉搜索树

代码随想录算法训练营第17天 | 复习二叉搜索树

时间:2024-07-22 16:21:14浏览次数:12  
标签:right TreeNode val 17 随想录 二叉 null root left

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

相关文章

  • [ARC176E] Max Vector 题解
    题目链接点击打开链接题目解法这个题的一个转化很关键:把一次操作\(j\)等价看作必须满足\((\forall_{1\lei\len}X_i\gea_{j,i})|(\forall_{1\lei\len}Y_i\gea_{j,i})=1\)正确性是显然的另外的一个关键思路是网络流有了上面的转化,我们考虑切糕模型(其实接下来都好想......
  • 「代码随想录算法训练营」第十七天 | 二叉树 part7
    235.二叉搜索树的最近公共祖先题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/题目难度:中等文章讲解:https://programmercarl.com/0235.二叉搜索树的最近公共祖先.html视频讲解:https://www.bilibili.com/video/BV1Zt4y1F7ww?share_so......
  • 代码随想录算法训练营第十一天| 144. 二叉树的前序遍历 , 94. 二叉树的中序遍历, 145.二
    今天主要学习了二叉树的基本概念,以及多种遍历方法。包含分别使用迭代思想和递归思想的前序遍历,中序遍历,后序遍历以及层次遍历。二叉树的基础知识二叉树二叉树的种类可以分为满二叉树和完全二叉树。满二叉树指的是一个二叉树仅包含度为0和度为2的结点,并且度为0的节点在同一层......
  • Java语言程序设计基础篇_编程练习题**15.17 (几何问题:寻找边界矩形)
    **15.17(几何问題:寻找边界矩形)请编写一个程序,让用户可以在一个二维面板上动态地增加和移除点,如图15-29a所示。当点加入和移除的时候,一个最小的边界矩形更新显示。假设每个点的半径是10像素解题思路:这道题可以从编程练习题15.15修改新建一个面板Pane(),方法外部新建一个......
  • 代码随想录算法训练营第一天leetcode704二分查找27移除元素
    leetcode704,这是leetcode提交四次后通过的结果:classSolution{  publicintsearch(int[]nums,inttarget){    if(nums.length==1&&nums[0]==target)      return 0;    if(nums.length==2)      if(nums[0]==target)......
  • Day 20 二叉树part07
    235.二叉搜索树的最近公共祖先总体上思想与236.二叉树的最近公共祖先思路是一致的,都是去搜索p,q的位置。这个大框架是最难理解的部分,具体可以再去看看236的题解。这道题在其基础上利用了搜索树的性质,当根节点的val大于pq两者时,就去左子树找结果即可;反之则去右子树中查找。当p,q一......
  • 代码随想录day6 | 242 有效字母异位词 349 两个数组交际 202 快乐数 1 两数之和
    hash表遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法242判断字母异位词关于字符串的遍历问题//什么情况下遍历的是rune[]int36类型,什么情况下遍历的是char字节类型?s:="Hello,世界"fori,r:=ranges{ fmt.Printf("Index:%d,Rune:%c,......
  • 代码随想录算法训练营第36天 | 动态规划基础2:62.不同路径、63.不同路径 II
    62.不同路径https://leetcode.cn/problems/unique-paths/submissions/548656029/代码随想录https://programmercarl.com/0062.不同路径.html63.不同路径IIhttps://leetcode.cn/problems/unique-paths-ii/description/代码随想录https://programmercarl.com/0063.不同路径......
  • Android14 - 前台服务、图片选择器 、OpenJDK 17、其他适配
    前台服务1.指定前台服务类型   以Android14(API级别34)或更高版本为目标平台的应用,需要为应用中的每项前台服务指定服务类型,因为系统需要特定类型的前台服务满足特定用例。具体介绍如下:   在Android10在 <service> 元素内引入了 android:foregroundService......
  • 嵌入式人工智能(17-基于树莓派4B的电机控制-伺服电机SG90)
    伺服电机主要适用于角度需要不断变化且可以保持的控制系统,常见的机械臂、多足机器人、遥控船、摄像头云台等都可以使用伺服电机来实现。1、简介伺服电动机又被称为执行电动机、舵机,如图9.4所示,是由直流电机、减速齿轮组、电位器和控制电路组成的,封装在一个便于安装的外壳里,......