代码随想录算法训练营第十四天|二叉树基础-二叉树迭代-二叉树

文章目录

  • 二叉树基础
    • 二叉树种类
      • 满二叉树
      • 完全二叉树
      • 二叉搜索树
      • 平衡二叉搜索树
    • 二叉树的存储方式
      • 链式存储
      • 顺序存储
    • 二叉树的遍历方式
    • 二叉树的定义
  • 二叉树的递归遍历
    • 144.二叉树的前序遍历
      • 代码：
    • 145.二叉树的后序遍历
      • 代码：
    • 94. 二叉树的中序遍历
      • 代码
  • 二叉树的迭代遍历
    • 前序遍历（迭代法）-中左右->中右左（模拟出入栈）
      • 代码
    • 后序遍历（迭代法）
      • 思路：
      • 代码：
    • 中序遍历（迭代法）
      • 代码：
  • 二叉树的统一迭代法-画图理解增加熟练
      • 前序遍历写法-右左中（反过来）
      • 中序遍历写法-右中左
    • 后序遍历-中右左

二叉树基础

二叉树种类

满二叉树

在这里插入图片描述

完全二叉树

在这里插入图片描述

二叉搜索树

在这里插入图片描述

平衡二叉搜索树

在这里插入图片描述

二叉树的存储方式

链式存储

在这里插入图片描述

顺序存储

在这里插入图片描述

二叉树的遍历方式

二叉树主要有两种遍历方式：

  1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
  2. 广度优先遍历：一层一层的去遍历。

这两种遍历是图论中最基本的两种遍历方式，后面在介绍图论的时候 还会介绍到。

那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

  1. 深度优先遍历
    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）
  2. 广度优先遍历
    • 层次遍历（迭代法）
      在深度优先遍历中：有三个顺序，前中后序遍历， 有同学总分不清这三个顺序，经常搞混，我这里教大家一个技巧。

这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。

看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式

  • 前序遍历：中左右
  • 中序遍历：左中右
  • 后序遍历：左右中
    在这里插入图片描述

二叉树的定义

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;
    }
}

二叉树的递归遍历

在这里插入图片描述

144.二叉树的前序遍历

前序遍历，中左右

代码：

/**
 * 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<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();//结果数组
        preorder(root,result);//开始从根节点遍历
        return result;
    }
    public void preorder(TreeNode root,List<Integer> res){
        if(root==null){
            return; //直接返回
        }
        res.add(root.val);//添加根节点
        preorder(root.left,res);
        preorder(root.right,res);
    }
}

145.二叉树的后序遍历

左右中

代码：

/**
 * 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<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postOrder(root,res);
        return res;
    }
    public void postOrder(TreeNode root,List<Integer> res){
        if(root==null){
            return;
        }
        postOrder(root.left,res);
        postOrder(root.right,res);
        res.add(root.val);
    }
}

94. 二叉树的中序遍历

左中右

代码

/**
 * 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<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inOrder(root,res);
        return res;
    }
    public void inOrder(TreeNode root,List<Integer> res){
        if(root==null){
            return;
        }
        inOrder(root.left,res);
        res.add(root.val);
        inOrder(root.right,res);
    }
}

二叉树的迭代遍历

前序遍历（迭代法）-中左右->中右左（模拟出入栈）

我们先看一下前序遍历。

前序遍历是中左右，每次先处理的是中间节点，
那么先将根节点放入栈中，
然后先将右孩子加入栈，再加入左孩子。

为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。

动画如下：
在这里插入图片描述

代码

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);//加入根节点
        while(!stack.isEmpty()){
            //中
            TreeNode node=stack.pop();//弹出根节点
            res.add(node.val);//储存根节点的数值
            //右
            if(node.right!=null){
                stack.push(node.right);
            }
            //左
            if(node.left!=null){
                stack.push(node.left);
            }
        }
        return res;
    }
}

后序遍历（迭代法）

思路：

前序遍历的数组储存是中左右，那么把函数翻转，则变成数组储存是中右左，再将数组进行翻转，则变成左右中。
在这里插入图片描述

代码：

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return res;
        }
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.left!=null){
                stack.push(node.left);
            }
            if(node.right!=null){
                stack.push(node.right);
            }
        }
        Collections.reverse(res);//反转数组
        return res;
    }
}

中序遍历（迭代法）

为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：

  1. 处理：将元素放进result数组中
  2. 访问：遍历节点
    分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

动画如下：
在这里插入图片描述

代码：

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

二叉树的统一迭代法-画图理解增加熟练

在这里插入图片描述

前序遍历写法-右左中（反过来）

/**
 * 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<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root!=null){
            stack.push(root);
        }
        while(!stack.isEmpty()){
            TreeNode node=stack.peek();//栈中的第一个节点
            if(node!=null){
                stack.pop();//弹出避免重复，下面再将右左中节点添加到栈中
                if(node.right!=null){//添加右节点，空节点不入栈
                    stack.push(node.right); 
                }
                if(node.left!=null){//添加左节点，空节点不入栈
                    stack.push(node.left);
                }
                stack.push(node);//添加中节点
                stack.push(null);//中节点还没有处理，添加空节点null做标记
            }else{
                stack.pop();//弹出null
                node=stack.peek();//重新取出栈中元素
                stack.pop();//取出后再弹出
                res.add(node.val);
            }
        }
        return res;
    }
}

中序遍历写法-右中左

/**
 * 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;
 *     }
 * }
 */
/**
 * 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<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root!=null){//先放入根节点
            stack.push(root);
        }
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();//查找第一个结点
            if(node!=null){
                stack.pop();//弹出重复节点，按顺序放入右中左
                if(node.right!=null){
                    stack.push(node.right);
                }
                stack.push(node);
                stack.push(null);
                if(node.left!=null){
                    stack.push(node.left);
                }
            }else{
                stack.pop();
                node = stack.peek();
                stack.pop();
                res.add(node.val);
            }
        }
        return res;
    }
}

后序遍历-中右左

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root!=null){//先放入根节点
            stack.push(root);
        }
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();//查找第一个结点
            if(node!=null){
                stack.pop();//弹出重复节点，按顺序放入中右左
                stack.push(node);
                stack.push(null);
                if(node.right!=null){
                    stack.push(node.right);
                }
                if(node.left!=null){
                    stack.push(node.left);
                }
            }else{
                stack.pop();
                node = stack.peek();
                stack.pop();
                res.add(node.val);
            }
        }
        return res;
    }
}

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

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

相关文章

LEETCODE 164破解闯关密码

LEETCODE 164破解闯关密码

class Solution { public:string crackPassword(vector<int>& password) { //在比较两个字符串大小时&#xff0c;其实是按照字典序逐个比较它们的字符。首先比较两个字符串的第一个字符&#xff0c;如果它们不相等&#xff0c;则可以根据它们的 ASCII 码大小确定它们…
阅读更多...
SpringBoot+MyBatis使用pagehelper分页插件及其注意事项（含解决分页不生效问题）

SpringBoot+MyBatis使用pagehelper分页插件及其注意事项（含解决分页不生效问题）

1 前言 近期在做项目的时候&#xff0c;遇到了一个问题&#xff1a;在使用MyBatis的分页插件&#xff08;pagehelper&#xff09;时&#xff0c;发现其分页不生效&#xff0c;找了许多方法才得以解决&#xff0c;故写下这篇文章记录一下&#xff0c;帮助跟我遇到同样问题的同学…
阅读更多...
Python lambda函数

Python lambda函数

Python是一种功能强大的编程语言&#xff0c;具有许多特性和工具&#xff0c;其中之一是Lambda函数。Lambda函数是一种轻量级的匿名函数&#xff0c;可以快速定义和使用小型函数&#xff0c;而无需显式命名。本文将深入探讨Python中的Lambda函数&#xff0c;包括其语法、用途、…
阅读更多...
聚醚醚酮（Polyether Ether Ketone）PEEK主要作用是什么？

聚醚醚酮（Polyether Ether Ketone）PEEK主要作用是什么？

聚醚醚酮&#xff08;Polyether Ether Ketone&#xff0c;PEEK&#xff09;在工程和高性能应用中具有广泛的应用&#xff0c;主要作用包括&#xff1a; 1.结构材料&#xff1a; PEEK因其优异的机械性能&#xff0c;包括高强度、高硬度和耐磨性&#xff0c;常被用作结构件的制造…
阅读更多...
node.js安装配置详细教程（附图-贼详细）

node.js安装配置详细教程（附图-贼详细）

一&#xff1a;下载 Node.js官网下载地址&#xff1a;Node.js — Download 选择自己需要的版本我用的Windows ps:如果想下载指定版本&#xff0c;点下面这个就可以选择想要的版本 二&#xff1a;安装 1.下载完成后&#xff0c;双击安装包开始安装 2.安装过程&#xff1a;一步…
阅读更多...
qt学习：tcp区分保存多个客户端

qt学习：tcp区分保存多个客户端

在前面文掌的tcp客服端服务端进行更改 qt学习&#xff1a;Network网络类tcp客户端tcp服务端-CSDN博客https://blog.csdn.net/weixin_59669309/article/details/135842933?spm1001.2014.3001.5501前面的服务端每次有新的客户端连接&#xff0c;就会覆盖掉原来的指针&#xff0…
阅读更多...
堆的概念，性质及其实现

堆的概念，性质及其实现

1.堆的概念及结构 如果有一个关键码的集合K { &#xff0c; &#xff0c; &#xff0c;…&#xff0c; }&#xff0c;把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中&#xff0c;并满足&#xff1a; < 且 < ( > 且 > ) i 0&#xff0c;1&#x…
阅读更多...
Vue2 - vue-virtual-scroller 长列表优化原理

Vue2 - vue-virtual-scroller 长列表优化原理

目录 1&#xff0c;效果展示2&#xff0c;原理2.1&#xff0c;滚动条的处理2.2&#xff0c;展示内容处理 3&#xff0c;实现 vue-virtual-scroller 1&#xff0c;效果展示 1w 条数据无压力&#xff0c;看下初始渲染时间 Rendering 对比&#xff1a; 2&#xff0c;原理 目标&a…
阅读更多...
多维时序 | Matlab实现DBO-BiLSTM蜣螂算法优化双向长短期记忆神经网络多变量时间序列预测

多维时序 | Matlab实现DBO-BiLSTM蜣螂算法优化双向长短期记忆神经网络多变量时间序列预测

多维时序 | Matlab实现DBO-BiLSTM蜣螂算法优化双向长短期记忆神经网络多变量时间序列预测 目录 多维时序 | Matlab实现DBO-BiLSTM蜣螂算法优化双向长短期记忆神经网络多变量时间序列预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.Matlab实现DBO-BiLSTM多变量时间序…
阅读更多...
ActiveMQ|01-ClassicArtemis功能介绍

ActiveMQ|01-ClassicArtemis功能介绍

接上篇-MQ消息队列主流消息服务规范及代表产品&#xff0c;ActiveMQ就是基于JMS消息服务规范的消息中间件组件&#xff0c;主要应用在分布式系统架构中&#xff0c;帮助构建高可用、 高性能、可伸缩的企业级面向消息服务的系统 本文速览&#xff1a; JMS对象模型ActiveMQ的功…
阅读更多...
关于axios给后端发送数据的问题

关于axios给后端发送数据的问题

这里需要用的插件&#xff1a;qs.js&#xff0c;是前端给后端发送的数组&#xff0c;需要序列化所以要用到这个插件&#xff0c;这里就提取连接在这里&#xff0c;需要的自提&#xff0c;需要导如进来&#xff0c;别忘记了 链接&#xff1a;https://pan.baidu.com/s/1qyD8v9wfd…
阅读更多...
极简云验证商业版已经开源源码

极简云验证商业版已经开源源码

极简云商业版已经开源 解绑卡密 查询卡密 总体来说还是很完善的 对接例子网盘里有 用户注册需要配置邮箱 上网页 QQ 邮箱标准版开启 SMTP 然后生成授权码后台发信邮箱里填就对了 实在不会配置邮箱的 可以下载网盘里的reg.php 把 reg.php 上传源码里的 user 目录 之后注册就不需…
阅读更多...
论文阅读《thanking frequency fordeepfake detection》

论文阅读《thanking frequency fordeepfake detection》

这篇论文从频域的角度出发&#xff0c;提出了频域感知模型用于deepfake检测的模型 整体架构图&#xff1a; 1.FAD&#xff1a; 频域感知分解&#xff0c;其实就是利用DCT变换&#xff0c;将空间域转换为频域&#xff0c;变换后的图像低频信息在左上角&#xff0c;高频信息在右…
阅读更多...
TCP 三次握手以及滑动窗口

TCP 三次握手以及滑动窗口

TCP 三次握手 简介&#xff1a; TCP 是一种面向连接的单播协议&#xff0c;在发送数据前&#xff0c;通信双方必须在彼此间建立一条连接。所谓的 “ 连接” &#xff0c;其实是客户端和服务器的内存里保存的一份关于对方的信息&#xff0c;如 IP 地址、端口号等。 TCP 可以…
阅读更多...
如何使用Stable Diffusion的ReActor换脸插件

如何使用Stable Diffusion的ReActor换脸插件

ReActor插件是从roop插件分叉而来的一个更轻便、安装更简单的换脸插件。操作简单&#xff0c;非常容易上手&#xff0c;下面我们就介绍一下&#xff0c;如何将ReActor作为stable diffusion的插件进行安装和使用。 一&#xff1a;安装ReActor插件 项目地址&#xff1a;https:/…
阅读更多...
Docker部署Stable-Diffusion-webui

Docker部署Stable-Diffusion-webui

前排提示&#xff1a;如果不想折腾&#xff0c;可直接跳到最后获取封装好的容器&#xff0c;一键运行 :D 前言 乘上AI生成的快车&#xff0c;一同看看沿途的风景。 启一个miniconda容器 docker run -itd -v 宿主机内SD项目路径:/tmp --gpus all --ipc host -p 7860:7860 con…
阅读更多...
15- OpenCV：模板匹配（cv::matchTemplate）

15- OpenCV：模板匹配（cv::matchTemplate）

目录 1、模板匹配介绍 2、cv::matchTemplate 3、模板匹配的方法&#xff08;算法&#xff09; 4、代码演示 1、模板匹配介绍 模板匹配就是在整个图像区域发现与给定子图像匹配的小块区域。 它可以在一幅图像中寻找与给定模板最相似的部分。 模板匹配的步骤&#xff1a; &a…
阅读更多...
windows 搜狗输入法几款 简洁皮肤

windows 搜狗输入法几款 简洁皮肤

预览 下载地址 见附件 使用方法 下载到本地&#xff0c;解压&#xff0c;双击直接使用 分流下载链接 windows搜狗输入法皮肤.zip - 蓝奏云
阅读更多...
SQL - 事务控制

SQL - 事务控制

SQL - 事务控制 文章目录 SQL - 事务控制TCL - 事务事务的边界事务的特性事务的应用 事务隔离等级MySQL支持四种隔离级别 TCL - 事务 **模拟场景&#xff1a;**生活当中转账是转账方账户扣钱&#xff0c;收账方账户加钱。用数据库操作来模拟现实转账。 数据库模拟&#xff1a…
阅读更多...
etcd未授权到控制k8s集群

etcd未授权到控制k8s集群

在安装完 K8s 后&#xff0c;默认会安装 etcd 组件&#xff0c;etcd 是一个高可用的 key-value 数据库&#xff0c;它为 k8s 集群提供底层数据存储&#xff0c;保存了整个集群的状态。大多数情形下&#xff0c;数据库中的内容没有加密&#xff0c;因此如果黑客拿下 etcd&#x…
阅读更多...
最新文章

Copyright @ 2022~2023