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

代码随想录算法训练营第20天 | 二叉搜索树中级

时间:2024-07-23 16:10:23浏览次数:15  
标签:right TreeNode val 随想录 二叉 return 20 else root

2024年7月22日

题235. 二叉搜索树的最近公共祖先
普通解法还是和普通的祖先一样求即可,再依据搜索树特性进行剪枝即可加速。

import java.util.*;

class Solution {

    Vector<TreeNode> vec1;
    Vector<TreeNode> vec2;
    int flag1 = 0;
    int flag2 = 0;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //把p和q的路径都打印出来,然后从头开始往后看,如果第n个开始不一样了,那么第n-1个节点就是祖先
        vec1 = new Vector<>();
        vec2 = new Vector<>();
        digui1(root,p);
        digui2(root,q);
        int i=0;
        if(root.val==p.val && p.val==q.val){
            return root;
        }
        TreeNode pre = root;
        while(true){
            if(i==vec1.size()||i==vec2.size()){
                break;
            }
            if(vec1.get(i).val==vec2.get(i).val){
                pre = vec1.get(i);
            }else{
                break;
            }
            i+=1;
        }
        return pre;
    }

    public void digui1(TreeNode root, TreeNode t){
        if(flag1==1){
            return;
        }
        if(root==null){
            //回溯
            return;
        }
        vec1.add(root);
        if(root.val==t.val){
            flag1=1;
            return;
        }
        if(t.val>root.val){
            digui1(root.right,t);
        }else{
            digui1(root.left,t);
        }
        
        
        if(flag1==0){
            vec1.remove(vec1.size()-1);
        }
        return;
    }

    public void digui2(TreeNode root, TreeNode t){
        if(flag2==1){
            return;
        }
        if(root==null){
            //回溯
            return;
        }
        vec2.add(root);
        if(root.val==t.val){
            flag2=1;
            return;
        }
        if(t.val>root.val){
            digui2(root.right,t);
        }else{
            digui2(root.left,t);
        }
        if(flag2==0){
            vec2.remove(vec2.size()-1);
        }
        return;
    }
}

可以背一下高效迭代法,很好理解:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果一起大于或者小于,就更新当前节点,如果一起等于或者一个大一个小于就统一返回root即可
        while (root != null) {
            if (root.val > p.val && root.val > q.val) {
                root = root.left;
            } else if (root.val < p.val && root.val < q.val) {
                root = root.right;
            } else {
                return root;
            }
        }
        return root;
    }
}

题701. 二叉搜索树中的插入操作
递归即可。

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null){
            return new TreeNode(val);
        }
        if(val>root.val){
            root.right = digui(root.right,val);
        }else{
            root.left = digui(root.left,val);
        }
        return root;
    }

    public TreeNode digui(TreeNode p, int val){
        if(p==null){
            return new TreeNode(val);
        }else{
            if(val>p.val){
                p.right = digui(p.right,val);
            }else{
                p.left = digui(p.left,val);
            }
            return p;
        }
    }
}

题450. 删除二叉搜索树中的节点
分类思考,递归多想一下就熟悉了,关键是处理左右子树都在的情况下,就是把左子树挪到右子树的最左下角即可。

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        root = del(root,key);
        return root;
        
    }

    public TreeNode del(TreeNode root, int val){
        if(root==null){
            return null;
        }else if(val>root.val){
            root.right = del(root.right,val);
            return root;
        }else if(val<root.val){
            root.left = del(root.left,val);
            return root;
        }else{
            //左右子树都空
            if(root.left==null && root.right==null){
                return null;
            }else if(root.left!=null && root.right==null){
                return root.left;
            }else if(root.left==null && root.right!=null){
                return root.right;
            }else{
                TreeNode cur = root.right;
                while(cur.left!=null){
                    cur = cur.left;
                }
                cur.left = root.left;
                return root.right;
            }
        }
    }


}

标签:right,TreeNode,val,随想录,二叉,return,20,else,root
From: https://www.cnblogs.com/hailicy/p/18318664

相关文章

  • [NOIP2008 提高组] 笨小猴(洛谷题号P1125)
    [NOIP2008提高组]笨小猴题目描述笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!这种方法的具体描述如下:假设maxn是单词中出现次数最多的字母的出现次数,minn是单词中出现次数最少的字母的......
  • DASCTF 2023六月挑战赛|二进制专项 PWN (下)
    DASCTF2023六月挑战赛|二进制专项PWN(下)1.can_you_find_me检查保护意料之中64位ida逆向只有add,和del功能不能show先看add吧最多申请10个堆块存在off_by_null漏洞,可以考虑unlink来进行堆块重叠del函数就没有UAF漏洞了1.首先想办法泄露出libc地址,因为本题libc是2.27......
  • NSSCTF-2021年SWPU联合新生赛
    [SWPUCTF2021新生赛]finalrce这道题目考察tee命令和转义符\这题主要是,遇到一种新的符号,"\"—转义符。我理解的作用就是在一些控制字符被过滤的时候,可以用转义符,让控制符失去原本的含义,变为字面量,但是作用不变。目录扫描得到1.txt文件,但是发现里面没有内容,利用tee命令可以......
  • CeiT(ICCV 2021, SenseTime)论文与代码解析
    paper:IncorporatingConvolutionDesignsintoVisualTransformersofficialimplementation:GitHub-coeusguo/ceit背景近年来,Transformer在自然语言处理(NLP)任务中取得了巨大的成功,并且开始有一些尝试将其应用于视觉领域。然而,纯Transformer架构在视觉任务中通常需要大量的......
  • 代码随想录算法训练营第18天 | 二叉搜索树进阶
    2024年7月20日题530.二叉搜索树的最小绝对差使用递归获取中序遍历,然后遍历一遍vector即可得到结果。importjava.util.*;classSolution{Vector<Integer>vec;publicintgetMinimumDifference(TreeNoderoot){//首先得到中序遍历的结果vec......
  • # 代码随想录算法训练营第38天 | 01背包问题:1049.最后一块石头的重量II(最多能装多少)、
    1049.最后一块石头的重量IIhttps://leetcode.cn/problems/last-stone-weight-ii/代码随想录https://programmercarl.com/1049.最后一块石头的重量II.html#算法公开课494.目标和https://leetcode.cn/problems/target-sum/description/代码随想录https://programmercarl.com......
  • 代码随想录day7 | 454 四数相加|| 383 赎金信 15 三数之和 18 四数之和
    454四个数相加==0funcfourSumCount(nums1[]int,nums2[]int,nums3[]int,nums4[]int)int{ //1.用哈希表存储nums1和nums2两者之和的所有可能情况 //2.遍历nums3和nums4两者之和的相反数,如果在哈希表中存在,则结果加上哈希表中的值 //3.返回结果 sum1:......
  • P3275 [SCOI2011] 糖果
    原题链接题解缩点+差分约束,求最小值故跑最长路无解的情况:存在正权环,由于是有向图,所以环上的元素在一个强连通分量内,判断强连通分量内存不存在有正权值的边,然后缩点,拓扑跑一圈缩点时要一个超级源点就可以只dfs一次了code#include<bits/stdc++.h>usingnamespacestd;#def......
  • MBR60200PT-ASEMI无人机专用MBR60200PT
    编辑:llMBR60200PT-ASEMI无人机专用MBR60200PT型号:MBR60200PT品牌:ASEMI封装:TO-247批号:最新恢复时间:35ns最大平均正向电流(IF):60A最大循环峰值反向电压(VRRM):200V最大正向电压(VF):0.85V~0.90V工作温度:-40°C~175°C芯片个数:2芯片尺寸:mil正向浪涌电流(IFMS):500AMBR60200PT特性:......
  • 力扣209. 长度最小的子数组C++、窗口写法
    给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl,numsl+1,...,numsr-1,numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。示例1:输入:target=7,nums=[2,3,1,2,4,3]......