双非本科准备秋招(15.3)—— 力扣二叉树

        今天学了二叉树结点表示法,建树代码如下。

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return String.valueOf(val);
    }
}

        我们建一棵树,然后使用递归的方式前中后序遍历(preOrder、inOrder、postOrder),再使用非递归方式遍历(traversal)。

public class Test {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                1,
                new TreeNode(2, new TreeNode(4, null, null), null),
                new TreeNode(3, new TreeNode(5, null, null), new TreeNode(6, null, null))
        );

        preOrder(root);
        inOrder(root);
        postOrder(root);

        traversal(root);
    }

建的树如下:

        递归深度遍历:

/**
     * 前序
     */
    public static void preOrder(TreeNode t){
        if(t == null) return;
        System.out.println(t.val);
        preOrder(t.left);
        preOrder(t.right);
    }

    /**
     * 中序
     */
    public static void inOrder(TreeNode t){
        if(t == null) return;
        inOrder(t.left);
        System.out.println(t.val);
        inOrder(t.right);
    }

    /**
     * 后序
     */
    public static void postOrder(TreeNode t){
        if(t == null) return;
        postOrder(t.left);
        postOrder(t.right);
        System.out.println(t.val);
    }

        非递归的方式

        使用以下代码可以通用前中后序的遍历。

    /**
     * 一套代码通用遍历,改造后序遍历
     */
    public static void traversal(TreeNode t){
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode pop = null;
        while(t != null || !stack.isEmpty()){
            if(t != null){
                //左子树还没处理
                System.out.println("前序: " + t.val);
                stack.push(t);
                t = t.left;
            }
            else{
                TreeNode peek = stack.peek();
                if(peek.right == null){
                    //右子树为空
                    System.out.println("中序: " + peek.val);
                    pop = stack.pop();
                    System.out.println("后序: " + pop.val);
                }
                else if(peek.right == pop){
                    //右子树处理完成
                    pop = stack.pop();
                    System.out.println("后序: " + pop.val);
                }
                else{
                    //右子树还没处理
                    System.out.println("中序: " + peek.val);
                    t = peek.right;
                }
            }
        }
    }

使用以上知识解决如下题目:

1、144. 二叉树的前序遍历 

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode pop = null;
        while(root != null || !stack.isEmpty()){
            if(root != null){
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            else{
                TreeNode peek = stack.peek();
                if(peek.right == null || peek.right == pop){
                    pop = stack.pop();
                }
                else{
                    root = peek.right;
                }
            }
        }
        return list;
    }
}

2、94. 二叉树的中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode pop = null;
        while(root != null || !stack.isEmpty()){
            if(root != null){
                stack.push(root);
                root = root.left;
            }
            else{
                TreeNode peek = stack.peek();
                if(peek.right == null){
                    list.add(peek.val);
                    pop = stack.pop();
                }
                else if(peek.right == pop){
                    pop = stack.pop();
                }
                else{
                    list.add(peek.val);
                    root = peek.right;
                }
            }
        }
        return list;
    }
}

3、145. 二叉树的后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode pop = null;
        while(root != null || !stack.isEmpty()){
            if(root != null){
                stack.push(root);
                root = root.left;
            }
            else{
                TreeNode peek = stack.peek();
                if(peek.right == null || peek.right == pop){
                    pop = stack.pop();
                    list.add(peek.val);
                }
                else{
                    root = peek.right;
                }
            }
        }
        return list;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/368203.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C++ | 部分和函数partial_sum的使用技巧

如果你需要处理一个数组的前缀和&#xff0c;或者数组中某一段元素的前缀和&#xff0c;你会怎么做呢&#xff1f; partial_sum函数是STL中的函数&#xff0c;用于计算范围的部分和&#xff0c;并从结果开始分配范围中的每个元素&#xff0c;range[first,last)中相应元素的部分…

MH-ET LIVE Boards(ATTiny88)实验一---点亮板载灯

MH-ET LIVE Boards(ATTiny88&#xff09;实验一点亮板载灯 在Arduino IDE中添加开发板资源包加入开发板json添加开发板 安装开发板驱动方法一&#xff1a;github下载2.0a4.rar方法二&#xff1a;开发板的package包中自带的2.0a4.rar安装驱动确认安装成功 blink.ino程序测试![在…

知识图谱嵌入学习在推理方法中的应用与挑战

目录 前言1 关系推理的嵌入模型1.1 嵌入模型介绍1.2 模型的差异1.3 嵌入模型的发展趋势 2 符号推理与向量推理3 嵌入模型的多样性4 强化学习与挑战5 元关系学习结论 前言 在人工智能领域&#xff0c;推理一直是关键任务之一。然而&#xff0c;传统的符号推理受限于人工定义&am…

【Vitis】Vitis HLS学习系列笔记 :第一个例程

在学习vitis的过程中一定要跑几个例程试试看&#xff0c;这中间遇到了几个小问题&#xff0c;记录下 有干货&#xff0c;请注意查收&#xff1a;作为新手&#xff0c;跑例程大概率会遇到问题&#xff0c;这里记录几个问题&#xff0c;如果刚好你也遇到&#xff0c;一定会帮到你…

每日一题——LeetCode1389.按既定顺序创建目标数组

方法一 splice 使用splice函数就可以在数组的指定索引位置添加元素 var createTargetArray function(nums, index) {let res[]for(let i0;i<nums.length;i){res.splice(index[i],0,nums[i])}return res }; 消耗时间和内存情况&#xff1a; 方法二 模拟 如果res[index[…

计算机网络——链路层(1)

计算机网络——链路层&#xff08;1&#xff09; 小程一言专栏链接: [link](http://t.csdnimg.cn/ZUTXU)前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家&#xff0c; [跳转到网站](https://www.captainbed.…

[每日一题] 02.03 - 质因数分解

质因数分解 枚举到n的平方根&#xff08;得包括平方根&#xff09; 偶数去除 import math n int(input()) if n % 2 0:print(max(n // 2,2)) else:for i in range(3,int(math.sqrt(n)) 1,2):if n % i 0:print(max(n // i,i))

2023年度总结 | 关于意义,爱与回望——写给清醒又无知的20岁

Hi&#xff0c;大家好&#xff0c;我是半亩花海&#xff0c;一名再普通不过的大学生。2023年&#xff0c;20岁&#xff0c;充实而零乱的一年&#xff0c;清醒又无知的一年。年末&#xff0c;最近的一些事儿也让我逐渐地有感而发&#xff0c;心静&#xff0c;除杂&#xff0c;思…

redis布隆过滤器(Bloom)详细使用教程

文章目录 布隆过滤器1. 原理2. 结构和操作3. 特点和应用场景4. 缺点和注意事项 应用-redis插件布隆过滤器使用详细过程安装以及配置springboot项目使用redis布隆过滤器下面是布隆过滤器的一些基础命令 扩展 布隆过滤器 Bloom 过滤器是一种概率型数据结构&#xff0c;用于快速判…

在低代码平台上实现精益软件开发:提高效率与灵活性的关键实践

什么是精益软件开发&#xff1f; 精益软件开发是一种敏捷的软件开发框架。它基于最小化浪费和最大化价值的原则。该框架基于最小可行产品策略运行&#xff0c;该策略强调交付具有基本基本功能的产品&#xff0c;然后根据收到的反馈进行迭代以即兴发挥并提供卓越。 精益软件开发…

编译opencv4.6问题汇总,第三方软件包见我发的资源

win10系统 python3.8.2&#xff0c;cmake-3.15.5-win64-x64&#xff0c;opencv4.6 编译方式见&#xff1a;OpenCV的编译 - 知乎 本文主要总结问题。赠人玫瑰手留余香。 问题1 Problem with installing OpenCV using Visual Studio and CMake (error code: MSB3073) 解决方法…

魔改冰蝎 —— 绕过检测,自动生成免杀后门

为什么要魔改工具&#xff1f; 生成的代码很容易被监测 生成的后门很容易被杀软杀掉 了解冰蝎流量特征 开启http代理&#xff0c;数据经过BP抓包进行分析数据 冰蝎数据包分析&#xff1a; 1、三个请求头固定 AcceptAccept-LanguageUser-Agent&#xff08;内部有十个&a…

VSCODE使用ssh远程连接时启动服务器失败问题

错误情况 ping服务器的ip可通并且使用terminal可以ssh连接到远程服务器。但使用vscode的remote-ssh时&#xff0c;在「输出」栏出现了一直报 Waiting for server log… 的情况&#xff01; 解决方法一 重置服务器设置&#xff0c;包括以下手段&#xff1a; 1.清理服务器端的…

问题:测风站应设置在平直的巷道中,其前后()范围内不得有障碍物和拐弯等局部阻力。 #微信#媒体

问题&#xff1a;测风站应设置在平直的巷道中&#xff0c;其前后&#xff08;&#xff09;范围内不得有障碍物和拐弯等局部阻力。 参考答案如图所示

windows安装配置anaconda 创建并激活自己的虚拟环境(亲测可行,装不好你打我)

一.下载 选择一&#xff1a;进入清华镜像选择过去的版本 https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/ 本人电脑配置不高&#xff0c;并且一般过去的版本比较稳定&#xff0c;因此保守起见选择2022年5月的版本。 选择二&#xff1a;进入官网&#xff0c;下载最…

备战蓝桥杯---搜索(应用基础1)

话不多说&#xff0c;直接看题&#xff1a; 显然&#xff0c;我们直接用深搜&#xff0c;我们可以先把空位用结构体存&#xff0c;然后打表存小方块&#xff0c;再用数组存行列。 下面是AC代码&#xff1a; #include<bits/stdc.h> using namespace std; int a[12][12];…

【Python小游戏】五子棋小游戏(完整代码)

文章目录 写在前面Tkinter简介五子棋小游戏游戏介绍程序设计运行结果注意事项写在后面写在前面 本期内容:基于tkinter开发一个五子棋小游戏 实验环境 python3.11及以上pycharmtkinterTkinter简介 Tkinter是Python中最常用的图形用户界面(GUI)库之一,用于创建窗口、对话框…

SqlSever查询某个表的列名称、说明、备注、注释,类型等信息

背景:在工程项目中,有时需要对数据查询进行展示,常规的表格展示虽然能解决大部分问题;但在数据量比较大的情况就如果一次完整的展示信息,势必会造成数据加载中增加耗时,影响数据的展示效果;常规的解决方案都是在数据加载中采取分页的模式,降低数据的加载耗时;但如果要…

Servlet(未完结~)

文章目录 前言1 Servlet简介2 Servlet初识2.1 Servlet开发流程2.2 配置欢迎页 3 Servlet案例开发!3.1 开发登录页3.2 开发后台Servlet3.3 配置Servlet 4 HttpServletRequest4.1 回顾http请求4.2 自定义servlet流程图4.3 HttpServletRequest4.4获取请求行信息4.5获取请求头信息4…

【成品论文57页】2024美赛F题成品论文57页+每一小问配套代码数据

基于数据预测下的减少非法野生动物贸易研究 近年来&#xff0c;非法野生动物贸易每年涉及的金额高达 265 亿美元&#xff0c;被认为是全球第四大 非法贸易。本文基于收集的数据&#xff0c; 对非法野生动物贸易进行研究。 问题一&#xff0c;为了确定五年项目的研究对象我们利用…