算法体系-12 第 十二 二叉树的基本算法 下

一 实现二叉树的按层遍历

1.1 描述

1）其实就是宽度优先遍历，用队列

2）可以通过设置flag变量的方式，来发现某一层的结束（看题目）看下边的第四题解答

1.2 代码

public class Code01_LevelTraversalBT {public static class Node {public int value;public Node left;public Node right;public Node(int v) {value = v;}}public static void level(Node head) {if (head == null) {return;}Queue<Node> queue = new LinkedList<>();queue.add(head);while (!queue.isEmpty()) {Node cur = queue.poll();System.out.println(cur.value);if (cur.left != null) {queue.add(cur.left);}if (cur.right != null) {queue.add(cur.right);}}}

二 实现二叉树的序列化和反序列化

2.1描述

1）先序方式序列化和反序列化

2）按层方式序列化和反序列化

将二叉树序力化为唯一的字符串叫序力化，字符串也能转出唯一的数二叉树叫反序力化

2.2 分析

2.3 前序列化代码

public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static Queue<String> preSerial(Node head) {Queue<String> ans = new LinkedList<>();pres(head, ans);return ans;}public static void pres(Node head, Queue<String> ans) {if (head == null) {ans.add(null);} else {ans.add(String.valueOf(head.value));pres(head.left, ans);pres(head.right, ans);}}

2.4 前序反序列化

public static Node buildByPreQueue(Queue<String> prelist) {if (prelist == null || prelist.size() == 0) {return null;}return preb(prelist);}public static Node preb(Queue<String> prelist) {String value = prelist.poll();if (value == null) {return null;}Node head = new Node(Integer.valueOf(value));head.left = preb(prelist);head.right = preb(prelist);return head;}

2.5 中序列化代码

由上图可以知道，中序序例化是有歧义的，所以不存在中序的序列化

public static Queue<String> inSerial(Node head) {Queue<String> ans = new LinkedList<>();ins(head, ans);return ans;}public static void ins(Node head, Queue<String> ans) {if (head == null) {ans.add(null);} else {ins(head.left, ans);ans.add(String.valueOf(head.value));ins(head.right, ans);}}

2.7 中序反列化 

2.8 后序列化代码

public static Queue<String> posSerial(Node head) {Queue<String> ans = new LinkedList<>();poss(head, ans);return ans;}public static void poss(Node head, Queue<String> ans) {if (head == null) {ans.add(null);} else {poss(head.left, ans);poss(head.right, ans);ans.add(String.valueOf(head.value));}}

2.9后序反列化代码

public static Node buildByPosQueue(Queue<String> poslist) {if (poslist == null || poslist.size() == 0) {return null;}// 左右中  ->  stack(中右左) 默认是左右中，这种情况没法首先没法建立头节点，因此进行转化为头在前面的情况，把它放入stack(中右左)，这是头就先出来，就可以新建headStack<String> stack = new Stack<>();while (!poslist.isEmpty()) {stack.push(poslist.poll());}return posb(stack);}public static Node posb(Stack<String> posstack) {String value = posstack.pop();if (value == null) {return null;}Node head = new Node(Integer.valueOf(value));head.right = posb(posstack);head.left = posb(posstack);return head;}

3.0 按层序列化和反序列化

3.0.1分析

3.0.2 按层序列化 代码

public static Queue<String> levelSerial(Node head) {Queue<String> ans = new LinkedList<>();if (head == null) {ans.add(null);} else {ans.add(String.valueOf(head.value));Queue<Node> queue = new LinkedList<Node>();queue.add(head);while (!queue.isEmpty()) {head = queue.poll(); // head 父   子if (head.left != null) {ans.add(String.valueOf(head.left.value));queue.add(head.left);} else {ans.add(null);}if (head.right != null) {ans.add(String.valueOf(head.right.value));queue.add(head.right);} else {ans.add(null);}}}return ans;}

3.0.3 按层反序列化 代码

public static Node buildByLevelQueue(Queue<String> levelList) {if (levelList == null || levelList.size() == 0) {return null;}Node head = generateNode(levelList.poll());Queue<Node> queue = new LinkedList<Node>();if (head != null) {queue.add(head);}//因为要记录上一次的节点，这里借用队列来完成Node node = null;while (!queue.isEmpty()) {node = queue.poll();node.left = generateNode(levelList.poll());node.right = generateNode(levelList.poll());if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}return head;}public static Node generateNode(String val) {if (val == null) {return null;}return new Node(Integer.valueOf(val));}

三 Encode N-ary Tree to Binary Tree

3.1 描述

一颗多叉树，序历化为为二叉树，二叉树也能转为原来的多叉树；

3.2 分析

第一步 先将多叉树的每个节点的孩子放在对应节点左树的右边界上；

左树的节点为该节点的第一个树，反回来看某个节点是否有孩子看该节点左数是否有右边孩子

结构如下

3.3 代码

package class11;import java.util.ArrayList;
import java.util.List;// 本题测试链接：https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree
public class Code03_EncodeNaryTreeToBinaryTree {// 提交时不要提交这个类public static class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}};// 提交时不要提交这个类public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}// 只提交这个类即可class Codec {// Encodes an n-ary tree to a binary tree.public TreeNode encode(Node root) {if (root == null) {return null;}TreeNode head = new TreeNode(root.val);head.left = en(root.children);return head;}private TreeNode en(List<Node> children) {TreeNode head = null;TreeNode cur = null;for (Node child : children) {TreeNode tNode = new TreeNode(child.val);if (head == null) {head = tNode;} else {cur.right = tNode;}cur = tNode;cur.left = en(child.children);}return head;}// Decodes your binary tree to an n-ary tree.public Node decode(TreeNode root) {if (root == null) {return null;}return new Node(root.val, de(root.left));}public List<Node> de(TreeNode root) {List<Node> children = new ArrayList<>();while (root != null) {Node cur = new Node(root.val, de(root.left));children.add(cur);root = root.right;}return children;}}}

四 求二叉树最宽的层有多少个节点

4.1 描述

打印二叉树每层的的节点树及最多的节点数；

4.2 分析

根据宽度优先遍历的基础上，要是能知道哪一层结束，那么就能算出每一层的节点数；

设计两个数，Node curEnd = head; // 当前层，最右节点是谁Node nextEnd = null; // 下一层，最右节点是谁

每次遍历当前节点时候，判断该节点是否和记录的curEnd节点相等，相等就是当前层结束了，把当前层的节点数更新到max中，

再将当前节点的每一个左右孩子更新到队列中的过程中，每一步都更新nextEnd的值为当前加队列的值，下一层遍历来的时候更新curEnd值为nextEnd

4.3 代码

public static int maxWidthNoMap(Node head) {if (head == null) {return 0;}Queue<Node> queue = new LinkedList<>();queue.add(head);Node curEnd = head; // 当前层，最右节点是谁Node nextEnd = null; // 下一层的最右节点是谁。提前为下一层出来的end节点做准备int max = 0;int curLevelNodes = 0; // 当前层的节点数while (!queue.isEmpty()) {Node cur = queue.poll();if (cur.left != null) {queue.add(cur.left);nextEnd = cur.left;}if (cur.right != null) {queue.add(cur.right);nextEnd = cur.right;}curLevelNodes++;if (cur == curEnd) {max = Math.max(max, curLevelNodes);curLevelNodes = 0;curEnd = nextEnd;}}return max;}//使用额外HashMapdpublic static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static int maxWidthUseMap(Node head) {if (head == null) {return 0;}Queue<Node> queue = new LinkedList<>();queue.add(head);// key 在 哪一层，valueHashMap<Node, Integer> levelMap = new HashMap<>();levelMap.put(head, 1);int curLevel = 1; // 当前你正在统计哪一层的宽度int curLevelNodes = 0; // 当前层curLevel层，宽度目前是多少int max = 0;while (!queue.isEmpty()) {Node cur = queue.poll();int curNodeLevel = levelMap.get(cur);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);}if (curNodeLevel == curLevel) {curLevelNodes++;} else {max = Math.max(max, curLevelNodes);curLevel++;curLevelNodes = 1;}}max = Math.max(max, curLevelNodes);return max;}

五 二叉树中的某个节点，返回该节点的后继节点

5.1 描述

后继节点 ：比如中序遍历，求该节点的4的后继节点，就是中序遍历遍历到该节点后的所有节点

二叉树结构如下定义：

Class Node {

V value;

Node left;

Node right;

Node parent;

}

给你二叉树中的某个节点，返回该节点的后继节点

5.2 分析 中序遍历

5.2.1 方案一 先通过parrent 找到的他的跟节点后，然后通root找到他的中序遍历，然后就可以找到该节点的后继节点

方案二

5.2.2 情况1一 如果该节点有右数，那么他的后继节点一定是他右树的最左侧节点

情况二 当该节点没有右树的时候，去找该节点是谁的节点左树的最右侧节点（中序遍历的本质理解）如果没有右子树，根据中序遍历的特点，下一个就应该是去找该节点是谁的节点左树的最右侧节点

情况二 讨论如下 找一个数的后继节点，一直往上找，通过找到该节点的最后一个父节点，该节点的右子树就是他的后继节点

如下，x是y左数的最右节点，所以打印完x就该打印y了 == 找的就是那个左树上的最右节点

5.3 代码

public class Code06_SuccessorNode {public static class Node {public int value;public Node left;public Node right;public Node parent;public Node(int data) {this.value = data;}}public static Node getSuccessorNode(Node node) {if (node == null) {return node;}if (node.right != null) {return getLeftMost(node.right);} else { // 无右子树Node parent = node.parent;while (parent != null && parent.right == node) { // 当前节点是其父亲节点右孩子node = parent;parent = node.parent;}return parent;}}public static Node getLeftMost(Node node) {if (node == null) {return node;}while (node.left != null) {node = node.left;}return node;}

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【python】flask服务端响应与重定向处理

【python】flask服务端响应与重定向处理

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…
阅读更多...
Spring单元测试+Mockito

Spring单元测试+Mockito

一&#xff0c;背景 单元测试基本上是开发逃不过的一个工作内容&#xff0c;虽然往往因为过于无聊&#xff0c;或者过于麻烦&#xff0c;而停止于项目的迭代之中&#xff0c;不了了之了。其实不是开发们懒&#xff0c;而是上头要求的测试覆盖率高&#xff0c;但是又没有好用的…
阅读更多...
大模型+强化学习_精典方法_RLHF

大模型+强化学习_精典方法_RLHF

英文名称&#xff1a;Deep Reinforcement Learning from Human Preferences 中文名称&#xff1a;从人类偏好中进行深度强化学习 链接&#xff1a;https://arxiv.org/abs/1706.03741 作者&#xff1a;Paul F Christiano, Jan Leike, Tom B Brown... 机构&#xff1a;OpenAI, …
阅读更多...
数据结构从入门到精通——快速排序

数据结构从入门到精通——快速排序

快速排序 前言一、快速排序的基本思想常见方式通用模块 二、快速排序的特性总结三、三种快速排序的动画展示四、hoare版本快速排序的代码展示普通版本优化版本为什么要优化快速排序代码三数取中法优化代码 五、挖坑法快速排序的代码展示六、前后指针快速排序的代码展示七、非递…
阅读更多...
英特尔生态的深度学习科研环境配置-A770为例

英特尔生态的深度学习科研环境配置-A770为例

之前发过在Intel A770 GPU安装oneAPI的教程&#xff0c;但那个方法是用于WSL上。总所周知&#xff0c;在WSL使用显卡会有性能损失的。而当初买这台机器的时候我不在场&#xff0c;所以我这几天刚好有空把机器给重装成Ubuntu了。本篇不限于安装oneAPI&#xff0c;因为在英特尔的…
阅读更多...
什么是PLC物联网关？PLC物联网关有哪些功能？

什么是PLC物联网关？PLC物联网关有哪些功能？

在数字化浪潮的推动下&#xff0c;工业物联网&#xff08;IIoT&#xff09;正逐步成为推动制造业智能化转型的关键力量。而在这一变革中&#xff0c;PLC物联网关扮演着至关重要的角色。今天&#xff0c;就让我们一起走进PLC物联网关的世界&#xff0c;了解它的定义、功能&#…
阅读更多...
41-Vue-webpack基础

41-Vue-webpack基础

webpack基础 前言什么是webpackwebpack的基本使用指定webpack的entry和output 前言 本篇开始来学习下webpack的使用 什么是webpack webpack: 是前端项目工程化的具体解决方案。 主要功能&#xff1a;它提供了友好的前端模块化开发支持&#xff0c;以及代码压缩混淆、处理浏览…
阅读更多...
机器学习 - 准备数据

机器学习 - 准备数据

“Data” in machine learning can be almost anything you can imagine. A table of big Excel spreadsheet, images, videos, audio files, text and more. 机器学习其实可以分为两部分 将不管是什么data&#xff0c;都转成numbers.挑选或者建立一个模型来学习这些numbers …
阅读更多...
js模版字符串-标签模版

js模版字符串-标签模版

模版字符串 js模版字符串使用来创建模版字符串字面量&#xff0c;例如 const name "yu" console.log(hello ${name})很多人都知道。但是其实我们可以定义标签函数来自定义返回结果。 标签函数 带标签的模板是模板字面量的一种更高级的形式&#xff0c;它允许你使…
阅读更多...
阿里云ecs服务器配置反向代理上传图片

阿里云ecs服务器配置反向代理上传图片

本文所有软件地址&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/12OSFilS-HNsHeXTOM47iaA 提取码&#xff1a;dqph 为什么要使用阿里云服务器&#xff1f; 项目想让别人通过外网进行访问就需要部署到我们的服务器当中 1.国内知名的服务器介绍 国内比较知名的一些…
阅读更多...
什么是行业垂直类媒体？有哪些？怎么邀约

什么是行业垂直类媒体？有哪些？怎么邀约

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体胡老师。 行业垂直类媒体是聚焦于特定行业或领域的媒体平台。 行业垂直类媒体不同于主流媒体&#xff0c;它们专注于提供与某个特定领域相关的深入内容和服务&#xff0c;例如商业新闻、旅游、数字…
阅读更多...
seleniumUI自动化实例（登录CSDN页面）

seleniumUI自动化实例（登录CSDN页面）

今天分享一个CSDN登录模块的登录场景 1.配置文件 CSDNconf.py&#xff1a; from selenium import webdriver options webdriver.ChromeOptions() options.binary_location r"D:\Program Files\360\360se6\Application\360se.exe" # 360浏览器安装地址 driver w…
阅读更多...
C++ Qt开发：QUdpSocket实现组播通信

C++ Qt开发：QUdpSocket实现组播通信

Qt 是一个跨平台C图形界面开发库&#xff0c;利用Qt可以快速开发跨平台窗体应用程序&#xff0c;在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置&#xff0c;实现图形化开发极大的方便了开发效率&#xff0c;本章将重点介绍如何运用QUdpSocket组件实现基于UDP的组播通信…
阅读更多...
MyBatis3源码深度解析(十七)MyBatis缓存(一)一级缓存和二级缓存的实现原理

MyBatis3源码深度解析(十七)MyBatis缓存(一)一级缓存和二级缓存的实现原理

文章目录 前言第六章 MyBatis缓存6.1 MyBatis缓存实现类6.2 MyBatis一级缓存实现原理6.2.1 一级缓存在查询时的使用6.2.2 一级缓存在更新时的清空 6.3 MyBatis二级缓存的实现原理6.3.1 实现的二级缓存的Executor类型6.3.2 二级缓存在查询时使用6.3.3 二级缓存在更新时清空 前言…
阅读更多...
Nginx 的安装、启动和关闭

Nginx 的安装、启动和关闭

文章目录 一、背景说明二、Nginx 的安装2.1、依赖的安装2.2、Nginx 安装2.3、验证安装 三、启动 Nginx3.1、普通启动3.2、如何判断nginx已启动3.3、通过配置启动3.4、设置开机启动 四、关闭 Nginx4.1、优雅地关闭4.2、快速关闭4.3、只关闭主进程4.4、使用nginx关闭服务 五、重启…
阅读更多...
计算机网络：数据交换方式

计算机网络：数据交换方式

计算机网络&#xff1a;数据交换方式 电路交换分组交换报文交换传输对比 本博客介绍计算机之间数据交换的三种方式&#xff0c;分别是电路交换、分组交换以及报文交换。 电路交换 我们首先来看电路交换&#xff0c;在电话问世后不久&#xff0c;人们就发现要让所有的电话机都…
阅读更多...
Springboot-软件授权License

Springboot-软件授权License

无意中看到了一个简单方便的授权方式&#xff0c;只需几步就可集成到boot项目中。 先上地址&#xff1a;smart-license: 保护个人与企业的软件作品权益&#xff0c;降低盗版造成的损失。PS&#xff1a;因个人精力有限&#xff0c;不再提供该项目的咨询答疑服务。 Smart-licen…
阅读更多...
【小米汽车SU7实测】 小米汽车su7到底行不行？小米新能源轿车体验感怎么样？

【小米汽车SU7实测】 小米汽车su7到底行不行？小米新能源轿车体验感怎么样？

小米汽车SU7是小米汽车的首款车型&#xff0c;定位“C级高性能生态科技轿车”&#xff0c;也是小米迈入新能源赛道的首次成果落地。 首先&#xff0c;让我们来谈谈它的性能。试驾过程中&#xff0c;小米SU7展现出了惊人的加速能力&#xff0c;0-100km/h加速仅需2.78秒&#xf…
阅读更多...
pytest全局配置+前后只固件配置

pytest全局配置+前后只固件配置

pytest全局配置前后只固件配置 通过读取pytest.ini配置文件运行通过读取pytest.ini配置文件运行无条件跳过pytest.initest_mashang.pyrun.py 有条件跳过test_mashang.py pytest框架实现的一些前后置&#xff08;固件、夹具&#xff09;处理方法一&#xff08;封装&#xff09;方…
阅读更多...
Kafka总结问题

Kafka总结问题

Kafka Kafka Kafka Kafka的核心概念/ 结构 topoic Topic 被称为主题&#xff0c;在 kafka 中&#xff0c;使用一个类别属性来划分消息的所属类&#xff0c;划分消息的这个类称为 topic。topic 相当于消息的分配标签&#xff0c;是一个逻辑概念。主题好比是数据库的表&#xff0…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023