首页 > 其他分享 >11.29打卡

11.29打卡

时间:2023-11-29 21:58:14浏览次数:46  
标签:node 11.29 right TreeNode val int 打卡 left

1. 从中序与后序遍历序列构造二叉树(106)

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

/**
 * 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 {
        private Map<Integer,Integer> map;
    private  int[] postorder;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
         this.postorder =postorder;
         map =  new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return dfsbuild(0,inorder.length-1,0,postorder.length-1);
    }
      private TreeNode dfsbuild(int instart, int inend , int poststart,int postend) {
        if(poststart>postend||inend<instart)
            return null;
        int rootval = postorder[postend];
        int inid=map.get(rootval);
        TreeNode root = new TreeNode(rootval);
        int leftnum = inid-instart;
        root.left=dfsbuild(instart,inid-1,poststart,poststart+leftnum-1);
        root.right=dfsbuild(inid+1,inend,poststart+leftnum,postend-1);
        return root;
    }
}

2.二叉树的层序遍历 II(107)

给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
/**
 * 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 List<List<Integer>> levelOrderBottom(TreeNode root) {
          LinkedList<List<Integer>> res =new LinkedList<>();
        if(root==null)return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
           for (int i =queue.size();i>0;i--){
                TreeNode node = queue.poll();
                list.add(node.val);
               
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
            queue.add(node.right);
            }
            res.addFirst(list);
        }
        return res;

    }
}

3. 将有序数组转成二叉搜索树(108)

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

/**
 * 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 sortedArrayToBST(int[] nums) {
        return build(0,nums.length-1,nums);
       
    }
    public TreeNode build(int start,int end, int[] nums){
        if(end<start)
            return null;
        int mid = (end-start)/2+start;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(start,mid-1,nums);
        root.right = build(mid+1,end,nums);
        return root;
    }
}

 

标签:node,11.29,right,TreeNode,val,int,打卡,left
From: https://www.cnblogs.com/forever-fate/p/17865977.html

相关文章

  • 11.29日记
    HarmonyOS是一款面向万物互联时代的、全新的分布式操作系统。在传统的单设备系统能力基础上,HarmonyOS提出了基于同一套系统能力、适配多种终端形态的分布式理念,能够支持手机、平板、智能穿戴、智慧屏、车机等多种终端设备,提供全场景(移动办公、运动健康、社交通信、媒体娱乐等)业务......
  • 11.29每日总结
    新建maven项目时,Run中报警告:Noarchetypefoundinremotecatalog.Defaultingtointernalcatalog.【在远程目录中没有找到原型。默认为内部编录。】,如图: 解决办法1:可以不用管【因为使用了maven模版构建项目,要从网上获取模版,然而没有找到这个模版或者网络慢,导致获取失败】,......
  • 11.29
    明天考试。今天写什么jb石子合并3,然后发现要优化,于是看了眼题解里写的都是四边形不等式。朴素N^3算法voidwork(inta[],intn){for(inti=0;i<n;++i)dpmin[i][0]=dpmax[i][0]=0;for(intj=1;j<n;++j)for(inti=0;i<n;++i){......
  • 11.29每日总结
    今天进行软件构造的实验一实验一:百度机器翻译SDK实验(2023.11.29日完成)任务一:下载配置百度翻译Java相关库及环境(占10%)。任务二:了解百度翻译相关功能并进行总结,包括文本翻译-通用版和文本翻译-词典版(占20%)。任务三:完成百度翻译相关功能代码并测试调用,要求可以实现中文翻译成英文......
  • 11.29闲话
    今天也是为了解LCA,然后学了树链剖分这边写个讲解树剖分为重链剖分和长链剖分通常指的是重链剖分重链剖分对于任意一个位于树上的节点重子节点表示其子节点中子树最大的子结点。如果有多个子树最大的子结点,取其一。如果没有子节点,就无重子节点。轻子节点表示剩余的所有子......
  • 每日总结11.29
    百度机器翻译SDK实验完成百度翻译GUI相关功能代码并测试调用,实现中文翻译成英文,英文翻译成中文。示例代码:packagebaidu.com;importokhttp3.*;importorg.json.JSONObject;importjava.io.*;classSample{publicstaticfinalStringAPI_KEY="";publics......
  • 2023.11.29 日记 Take it easy
    很不想把文化课写到日记里。但今天有点烦了。考试考的内容是要通过刷题得知的,并非学习。我已经在别的平台抱怨过很多次当今教育现状了,无济于事是肯定的,反而会打消学习的积极性。由于训练原因欠了很多课,再加上两个学校的进度不同、考试时间不同,我的学习成果实在像是被虫蛀了一样......
  • 23.11.29(代码大全2读书笔记)
    *第一部分打好基础 第一章欢迎进入软件构建的世界 >软件构建的定义:包括编码与调试、单元测试、规划构建、集成等,没有给出一个明确的定义。>软件构建的重要性:软件构建是编写大型项目最重要的、不可或缺的部分。 第二章用隐喻来更充分地理解软件开发 > 对软件开......
  • 11.29-task5-代码风格
    代码风格代码风格介绍修饰代码的前提是代码没有bug。。。两幅图中的代码对比,显然后一幅图的代码更加简洁,易懂。也方便之后很长时间后的再理解。缩进tab==4个空格当函数有多参数时换行当一个语句的字符数过长,要换行运算符对齐导入规范导入时要遵循同级文......
  • 聪明办法学python-11.27——11.29笔记打卡
    一、python中条件语句的应用总体代码结构为:ifTrue:dosomethingelse:doother简单描述为“True”为条件,当条件为真的时候,执行“dosomething”,否则就执行“doother”。例如:任务:实现一个函数,返......