数据结构与算法：二叉树（前中后三种遍历的递归和非递归原理和板子、判断是否为搜索二叉树BST、完全二叉树、满二叉树、平衡二叉树）

二叉树递归遍历原理

递归序

很有意思的一个全新的角度：从递归序去看前中后三种遍历。

首先来看一颗二叉树：
在这里插入图片描述
和其遍历的函数

    public static void recurtion(Node head){
        //第一步入口
        if(head==null) 
        return;
        //第一步出口
        //第二步入口
        recurtion(head.left);
        //第二步出口
        //第三步入口
        recurtion(head.right);
        //第三步出口
    }

那么这颗树的递归序便是1，2，4，4，4，2，5，5，5，2，1，3，6，6，6，3，7，7，7，3，1
可以看到，任何一颗二叉树的节点的递归序实际上都会经过其自身三次。
前序遍历、中序遍历、后续遍历就是在这三次中选取不同时候进行处理而已。
譬如前序遍历便是经过自身第一次时就进行处理，这里假设为简单打印。
那么就能很快地得到前序遍历的顺序为：1，2，4，5，3，6，7
同理，中序遍历就是经过自身第二次时进行处理，其他时候不做处理。
后序遍历就是经过自身第三次时进行处理，其他时候不做处理。

前中后序遍历递归板子

    public static void preOrderTraversal(Node head){
        if(head==null) return;
        System.out.println(head.val);
        preOrderTraversal(head.left);
        preOrderTraversal(head.right);
    }

    public static void inOrderTraversal(Node head){
        if(head==null) return;
        preOrderTraversal(head.left);
        System.out.println(head.val);
        preOrderTraversal(head.right);
    }

    public static void postOrderTraversal(Node head){
        if(head==null) return;
        preOrderTraversal(head.left);
        preOrderTraversal(head.right);
        System.out.println(head.val);
    }

二叉树非递归遍历板子实现

二叉树非递归的实现都是通过栈。我们通过手动压栈来替代系统压栈的过程。

前序遍历（同时也是深度优先遍历）

因为前序遍历是“根左右”，而栈的进出顺序是反的，所以需要先进右节点，再进左节点。至于根节点，因为我们都是通过根节点访问到的左节点、右节点，那么只要是每次只入栈一个节点，并在栈不为空的循环里面进行处理的，根节点都是最先处理的。

    public static void preOrderTraversal(Node head){
        if(head==null) return;
        Stack<Node> stack = new Stack<>();
        stack.add(head);
        whille(!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.println(cur.val);
            if(cur.right!=null) stack.add(cur.right);
            if(cur.left!=null) stack.add(cur.left);
        }
    }

后序遍历

因为后序遍历要求是“左右根”，所以只有一个栈是不够的。因为只要是每次入栈只有一个节点，且在栈非空循环里进行处理的，那么最开始进栈并处理的一定是根节点，所以我们需要两个栈，称为A栈和B栈（B站？乐）。那么顺序1经过A栈，会变成顺序1的反顺序，再经过B栈，又会变为顺序1。由此可以得知，我们最开始放入A栈时的顺序就应该是“左右根”。

    public List<Integer> postorderTraversal(TreeNode root) {
        if(root==null) return new ArrayList<>(0);
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            stack2.add(cur);
            if(cur.left!=null) stack.add(cur.left);
            if(cur.right!=null) stack.add(cur.right);
        }
        while(!stack2.isEmpty()){
            TreeNode cur = stack2.pop();
            ans.add(cur.val);
        }
        return ans;
    }

中序遍历

中序遍历要求的是“左根右”，这不能单纯通过加栈来使根变为第一个顺序了，那么这又该怎么办呢？还记得我们在先序遍历时说过“只要是每次只入栈一个节点，并在栈不为空的循环里面进行处理的，根节点都是最先处理的”吗？这次我们每次入栈时入栈多个节点。
我们将根节点的所有左边界节点都入栈，然后弹出时检查是否有右树，有的话再次判断该右树是否有左边界，如有则全部入栈，没有的话右边界自身进栈，周而复始。
具体原理可以看左程云b站视频

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null)
            return new ArrayList<>(0);
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.add(root);
                root = root.left;
            } else {
                root = stack.pop();
                ans.add(root.val);
                root = root.right;
            }
        }
        return ans;
    }

二叉树的其他遍历

层序遍历（偶尔也叫宽度优先遍历）

第一版板子

用队列实现，先放左节点后放右节点，弹出时进行处理（这里简化为打印）。

    public void levelOrder(TreeNode root) {
        if(root==null) return ans;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.println(cur.val);
            if(cur.left!=null)                queue.add(cur.left);
            if(cur.right!=null)                queue.add(cur.right);
        }
    }

但是稍微复杂点的层序遍历就不行了，譬如它不知道哪几个节点是同一层的，无法求出这颗二叉树的最大宽度，像是LC102和LC662这种题就做不了。

第二版（不建议背）

为此有第二版板子，左神给的，如下，但不建议背，建议直接看本人的第三版板子。

public int widthOfBinaryTree(TreeNode root) {
        if(root==null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        int curlevel = 1;
        int curlevelnums = 0;
        int maxnums = -1;
        HashMap<TreeNode,Integer> levelmap = new HashMap<>();
        levelmap.put(root,1);
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            int curNodelevel = levelmap.get(cur);
            if(curNodelevel==curlevel){
                curlevelnums++;
            }else{
                maxnums=Math.max(maxnums, curlevelnums);
                curlevel++;
                curlevelnums=1;
            }
            if(cur.left!=null){
                levelmap.put(cur.left,curNodelevel+1);
                queue.add(cur.left);
            }
            if(cur.right!=null){
                levelmap.put(cur.right,curNodelevel+1);
                queue.add(cur.right);
            } 
        }
        maxnums=Math.max(maxnums, curlevelnums);//左神在B站上少了这一步，实际应该加上
        //避免最后一层没有和maxnums比较。
        return maxnums;
    }

第三版板子

public int widthOfBinaryTree(TreeNode root) {
        if(root==null) return 0;
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            list = new ArrayList<>();
            int size = queue.size();//获取到的队列的长度，便是这一层节点的数量。
            for(int i=0;i<size;i++){
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if(cur.left!=null)   queue.add(cur.left);
                if(cur.right!=null)  queue.add(cur.right);
            }
            ans.add(list);
        }
        int max = -1;
        for(List<Integer> li:ans){
            max=Math.max(max,li.size());
        }
        return max;
    }

统计特殊的二叉树最大宽度（LC662）

可以发现上述的第三版板子也是解决不了LC662这道题的，具体可看本人的另一篇博客：http://t.csdnimg.cn/TBwdy

相关题

LeetCode94.二叉树的中序遍历
LeetCode144.二叉树的前序遍历
LeetCode145.二叉树的后序遍历
LeetCode102.二叉树的层序遍历
LeetCode662.二叉树最大宽度

二叉树的判断

判断一棵二叉树是否是搜索二叉树？

搜索二叉树，又叫查找二叉树，英文简称为BST。

板子1

如果一棵树中序遍历时的顺序是递增或者严格不降的，那么他就是BST。

    public long preVal = Long.MIN_VALUE;  
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        boolean isLeftBst = isValidBST(root.left);
        if(!isLeftBst) return false;
        if(root.val<=preVal) return false;
        else preVal = root.val;
        return isValidBST(root.right);
    }

板子2（二叉树统一套路）

递归角度思考，如果一颗树根节点为root，它的左树是搜索二叉树，右树是搜索二叉树，且左树的最大值不超过root的值，右树的最小值不小于root的值。对于每个节点都是如此，那么这棵树就是BST。
为此，我们发现左树需要返回的信息有

  • 是否是搜索二叉树
  • 最大值

右树需要的返回的信息有

  • 是否是搜索二叉树
  • 最小值

为此， 我们统归一个结构体，里面返回

  • 是否是搜索二叉树
  • 最大值
  • 最小值
public class ReturnType{
        public boolean isBST;
        public int max;
        public int min;
        public ReturnType(boolean isBST, int max, int min){
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        } 
    }
    //递归函数
    public ReturnType check(TreeNode root){
        if(root==null) return null;
        ReturnType leftReturn = check(root.left);
        ReturnType rightReturn = check(root.right);
        if(leftReturn!=null){
            if(leftReturn.max>=root.val||leftReturn.isBST==false){
                return new ReturnType(false,root.val,root.val);
            }
        }
        if(rightReturn!=null){
            if(rightReturn.min<=root.val||rightReturn.isBST==false){
                return new ReturnType(false,root.val,root.val);
            }
        }
        int max=(rightReturn==null?root.val:rightReturn.max);
        int min=(leftReturn==null?root.val:leftReturn.min);
        return new ReturnType(true,max,min);
    }

    //主函数入口
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        return check(root).isBST;
    }

判断一棵二叉树是否是完全二叉树？

如果一颗树，按照层序遍历，应该满足如下条件

  • 不存在只有右孩子，没有左孩子的节点
  • 第一次出现左右孩子不全的节点之后的节点，都应该是叶子节点。
    public boolean isCompleteTree(TreeNode root) {
        boolean flag = false;
        if(root==null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(
                (flag==true&&!(cur.left==null&&cur.right==null))
       //flag为true，说明之前有遇到有左右孩子不全的节点。那么之后遍历到的节点都应该是叶子节点
                ||
                (cur.left==null&&cur.right!=null)//只有右孩子，没有左孩子的节点
                )
            return false;
            if(cur.left==null||cur.right==null) flag=true;
            if(cur.left!=null) queue.add(cur.left);
            if(cur.right!=null) queue.add(cur.right);
        }
        return true;
    }

判断一颗二叉树是否为满二叉树？（二叉树统一套路）

递归角度思考，如果一颗树根节点为root，其最大高度h和节点数nums满足nums=2^h-1。那么我们称这棵树为满二叉树。所以对于左树和右树，我们都需要返回其最大高度和节点数，这样才好更新根节点的最大高度和节点数。

public class Return{
        public int height;
        public int nodeNums;
        public Return(int height,int nodeNums){
            this.height=height;
            this.nodeNums=nodeNums;
        }
    }
    public Return process(TreeNode root){
        if(root==null) return new Return(0,0);
        Return leftReturn = process(root.left);
        Return rightReturn = process(root.right);
        int height = Math.max(leftReturn.height,rightReturn.height)+1;
        int nodeNums = leftReturn.nodeNums+rightReturn.nodeNums+1;
        return new Return(height,nodeNums);
    }
    public boolean isFullTree(TreeNode root) {
        if(root==null) return true;
        Return rootReturn = process(root);
        return (nodeNums==(1<<height)-1);//1<<n表示2的n次方
    }

判断是否为平衡二叉树？（二叉树统一递归套路）

递归角度思考，如果一颗树根节点的左孩子都是平衡二叉树，右孩子都是平衡二叉树，且左孩子和右孩子的最大高度之差的绝对值≤1，所有节点都如此，那么这棵树就是平衡二叉树。
所以我们知道左孩子和右孩子统一返回的信息有1.是否是平衡二叉树 2.最大高度

    public class Return{
        public boolean isBalanced;
        public int height;
        public Return(boolean isBalanced, int height){
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        return check(root).isBalanced;
    }

    public Return check(TreeNode root){
        if(root==null) return new Return(true,0);
        Return leftReturn = check(root.left);
        Return rightReturn = check(root.right);
        boolean isBalanced = true;
        int height = 1;
        int leftHeight = 1;
        int rightHeight = 1;
        if(leftReturn!=null){
            if(leftReturn.isBalanced==false) return new Return(false,1);
            leftHeight=leftReturn.height;
        }
        if(rightReturn!=null){
            if(rightReturn.isBalanced==false) return new Return(false,1);
            rightHeight = rightReturn.height;
        }
        isBalanced = (Math.abs(leftHeight-rightHeight)<2);
        height = Math.max(leftHeight,rightHeight)+1;
        return new Return(isBalanced,height); 
    }

相关题

LeetCode 98.验证二叉搜索树
LeetCode 176. 判断是否为平衡二叉树
LeetCode 110. 平衡二叉树
LeetCode 958. 二叉树的完全性检验

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

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

相关文章

第七篇：SQL语法-DML-数据操作语言

第七篇：SQL语法-DML-数据操作语言

DML英文全称是Data Manipulation Language(数据操作语言)&#xff0c;用来对数据库中表的数据记录进行增删改操作。它主要包含以下操作&#xff0c; 添加数据(INSERT)修改数据(UPDATE)删除数据(DELETE) 一&#xff0c;添加数据(INSERT) 注意&#xff1a; 插入数据时&#xff0c…
阅读更多...
LeetCode:70.爬楼梯

LeetCode:70.爬楼梯

前言&#xff1a;好家伙&#xff0c;一直以为动态规划是啥高大上的&#xff0c;解释那么多&#xff0c;在我看来不过是找规律罢了&#xff0c; 写那么多"专业术语"咋看咋像糊弄人的 (手动扶额) 另外&#xff0c;通项公式虽然抽象还能接受&#xff0c;但是矩阵快速幂…
阅读更多...
08:K8S资源对象管理｜服务与负载均衡｜Ingress

08:K8S资源对象管理｜服务与负载均衡｜Ingress

K8S资源对象管理&#xff5c;服务与负载均衡&#xff5c;Ingress DaemonSet控制器污点策略容忍容忍污点 其他资源对象Job资源对象 有限生命周期CronJob资源对象 集群服务服务自动发现headless服务 实现服务定位与查找 服务类型 Ingress插件 发布服务的方式 DaemonSet控制器 Da…
阅读更多...
洛谷: P9749 [CSP-J 2023] 公路

洛谷: P9749 [CSP-J 2023] 公路

思路: 贪心思想指的是在对问题求解的时候&#xff0c;总是能做出在当前看来是最好的选择,也就是说&#xff0c;如果要得到整个问题的最优答案&#xff0c;那么要求每一步都能做出最好的选择&#xff08;feihua&#xff09;。 在这道题里面&#xff0c;我们希望在来到第i站的时…
阅读更多...
iTop-4412 裸机程序（十九）- 按键中断

iTop-4412 裸机程序（十九）- 按键中断

目录 0.源码1.异常向量表1.1 原理1.2 异常种类1.3 ARMv7 规定的异常向量表 2. 中断2.1 iTop-4412 中使用的中断相关寄存器 上篇博文介绍了按键的轮询处理方式&#xff0c;本篇介绍按键的中断方式。 0.源码 GitHub&#xff1a;https://github.com/Kilento/4412NoOS 1.异常向量…
阅读更多...
微信小程序（四十四）鉴权组件插槽-登入检测

微信小程序（四十四）鉴权组件插槽-登入检测

注释很详细&#xff0c;直接上代码 新增内容&#xff1a; 1.鉴权组件插槽的用法 2.登入检测示范 源码&#xff1a; app.json {"usingComponents": {"auth":"/components/auth/auth"} }app.js App({globalData:{//定义全局变量isLoad:false} })…
阅读更多...
C++ Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统（1）

C++ Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统（1）

目标&#xff1a;旨在开发一个用户友好的软件工具&#xff0c;用于协助用户基于输入对象的成绩数据进行排序。该工具的特色在于&#xff0c;新输入的数据将以红色高亮显示&#xff0c;从而直观地展现出排序过程中数据变化的每一个步骤。 结果展示&#xff1a; 本程序是一个基于…
阅读更多...
在Ubuntu22.04上部署FoooCUS2.1

在Ubuntu22.04上部署FoooCUS2.1

Fooocus 是一款基于 Gradio的图像生成软件&#xff0c;Fooocus 是对 Stable Diffusion 和 Midjourney 设计的重新思考&#xff1a; 1、从 Stable Diffusion 学习&#xff0c;该软件是离线的、开源的和免费的。 2、从 Midjourney 中学到&#xff0c;不需要手动调整&#xff0c;…
阅读更多...
嵌入式Qt 计算器界面设计代码重构

嵌入式Qt 计算器界面设计代码重构

一.计算器界面设计代码重构 计算器界面设计&#xff1a;嵌入式Qt 计算器界面设计-CSDN博客 重构的概念&#xff1a; 代码实现与代码重构的不同&#xff1a; 软件开发过程&#xff1a; 什么样的代码需要重构&#xff1a; 计算器界面代码重构的框架设计&#xff1a; 实验&#…
阅读更多...
理解JAVA命名和目录接口（JNDI）

理解JAVA命名和目录接口（JNDI）

理解JAVA命名和目录接口（JNDI） 考虑访问网站的场景，Web用户要求记住四字节的IP地址而不是有意义的名称。例如，假设Web用户用123.23.3.123而不是hotmail.com访问hotmail网站。在这种情形下，Web用户难以记住不同的IP地址来访问不同的网站。因此，要使其变得对Web用户简单方…
阅读更多...
Unity下使用Sqlite

Unity下使用Sqlite

sqlite和access类似是文件形式的数据库&#xff0c;不需要安装任何服务&#xff0c;可以存储数据&#xff0c;使用起来还是挺方便的。 首先需要安装DLL 需要的DLL 我们找到下面两个文件放入Plugins目录 Mono.Data.Sqlite.dll System.Data.dll DLL文件位于Unity的安装目录下的…
阅读更多...
分布式文件系统 SpringBoot+FastDFS+Vue.js

分布式文件系统 SpringBoot+FastDFS+Vue.js

分布式文件系统 SpringBootFastDFSVue.js 一、分布式文件系统1.1.文件系统1.2.什么是分布式文件系统1.3.分布式文件系统的出现1.3.主流的分布式文件系统1.4.分布式文件服务提供商1.4.1.阿里OSS1.4.2.七牛云存储1.4.3.百度云存储 二、fastDFS2.1.fastDSF介绍2.2.为什么要使用fas…
阅读更多...
第4讲 小程序首页实现

第4讲 小程序首页实现

首页 create.vue <template><view class"vote_type"><view class"vote_tip_wrap"><text class"type_tip">请选择投票类型</text><!-- <text class"share">&#xe739;分享给朋友</text&g…
阅读更多...
如何在C# Windows Forms应用程序中实现控件之间的连接线

如何在C# Windows Forms应用程序中实现控件之间的连接线

帮我实现绘图工具多个控件连接线&#xff0c;请用c#代码实现 实现绘图工具中多个控件之间的连接线功能&#xff0c;可以通过以下几个步骤来进行&#xff1a; 定义连接线的数据模型&#xff1a;首先需要定义一个模型来表示连接线&#xff0c;这个模型应该包含起点和终点的坐标。…
阅读更多...
JavaScript中有哪些不同的数据类型

JavaScript中有哪些不同的数据类型

在 JavaScript 中&#xff0c;数据类型是一种用来表示数据的分类&#xff0c;它决定了我们可以对这个数据类型执行哪些操作。在 JavaScript 中有以下几种不同的数据类型&#xff1a; 基本数据类型 字符串 (String)&#xff1a;表示一组字符&#xff0c;可以使用引号&#xff08…
阅读更多...
Pytorch的可视化

Pytorch的可视化

1 使用 wandb进行可视化训练过程 本文章将从wandb的安装、wandb的使用、demo的演示进行讲解。 1.1 如何安装wandb&#xff1f; wandb的安装比较简单&#xff0c;在终端中执行如下的命令即可&#xff1a; pip install wandb在安装完成之后&#xff0c;我们需要&#xff0c;去…
阅读更多...
华为机考入门python3--（13）牛客13-句子逆序

华为机考入门python3--（13）牛客13-句子逆序

分类&#xff1a;列表 知识点&#xff1a; 列表逆序&#xff08;和字符串逆序是一样的&#xff09; my_list[::-1] 题目来自【牛客】 def reverse_sentence(sentence): # 将输入的句子分割words sentence.split() # 将单词逆序排列 words words[::-1] # 将单词用空…
阅读更多...
DarkSide针对VMware EXSI系统进行加密

DarkSide针对VMware EXSI系统进行加密

前言 最近黑客组织利用DarkSide勒索病毒对Colonial Pipeline 发起勒索攻击&#xff0c;国内外各大安全厂商和安全媒体也都有相关报道&#xff0c;DarkSide勒索软件是从2020年8月出现&#xff0c;并以(RAAS)勒索即服务的商业模式进行运作&#xff0c;此勒索病毒不仅可以部署基于…
阅读更多...
【Chrono Engine学习总结】5-sensor-5.1-sensor基础并创建一个lidar

【Chrono Engine学习总结】5-sensor-5.1-sensor基础并创建一个lidar

由于Chrono的官方教程在一些细节方面解释的并不清楚&#xff0c;自己做了一些尝试&#xff0c;做学习总结。 1、Sensor模块 Sensor模块是附加模块&#xff0c;需要单独安装。参考&#xff1a;【Chrono Engine学习总结】1-安装配置与程序运行 Sensor Module Tutorial Sensor …
阅读更多...
MySQL数据库⑧_索引（概念+理解+操作）

MySQL数据库⑧_索引（概念+理解+操作）

目录 1. 索引的概念和价值 1.1 索引的概念 1.2 索引的价值 2. 磁盘的概念 2.1 磁盘的结构 2.2 操作系统与磁盘交互的基本单位 2.3 MySQL与磁盘交互的基本单位 3. 索引的理解 3.1 主键索引现象和推导 3.2 索引采用的数据结构&#xff1a;B树 3.3 聚簇索引和非聚簇索引…
阅读更多...
最新文章

Copyright @ 2022~2023