Java数据结构第十五期:走进二叉树的奇妙世界(四)

专栏:Java数据结构秘籍

个人主页:手握风云

目录

一、二叉树OJ练习题(续)

1.1. 二叉树的层序遍历

1.2. 二叉树的最近公共祖先

1.3. 从前序与中序遍历序列构造二叉树

1.4. 从中序与后序遍历序列构造二叉树

1.5. 根据二叉树创建字符串

一、二叉树OJ练习题(续)

1.1. 二叉树的层序遍历

     层序遍历,就是从左到右依次访问每个节点。这里我们要借助队列来非递归方式的实现。我们先将根结点root放入队列,再用cur引用来接收弹出的根结点最后再打印。当左右子树不为空时,再一次将左子树和右子树放入队列中。然后先弹出左子树,如果左子树的左右结点不为空,再次放入。当队列为空时,遍历过程结束。所以下面这棵二叉树的打印结果应为“4271369”。

import java.util.LinkedList;
import java.util.Queue;class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right import java.util.LinkedList;
import java.util.Queue;class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public void levelOrder(TreeNode root){Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while(! queue.isEmpty()){TreeNode cur = queue.poll();System.out.print(cur.val+" ");if(cur.left != null){queue.offer(cur.left);}if(cur.right != null){queue.offer(cur.right);}}}
}= right;}
}public class Solution {public void levelOrder(TreeNode root){Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while(! queue.isEmpty()){TreeNode cur = queue.poll();System.out.print(cur.val+" ");if(cur.left != null){queue.offer(cur.left);}if(cur.right != null){queue.offer(cur.right);}}}
}
public class Test {public static void main(String[] args) {TreeNode root = new TreeNode(4,new TreeNode(2),new TreeNode(7));root.left.left = new TreeNode(1);root.left.right = new TreeNode(3);root.right.left = new TreeNode(6);root.right.right = new TreeNode(9);Solution solution = new Solution();solution.levelOrder(root);}
}

       但题目当中给出的类型是嵌套List<List<Integer>>,同时根据输出的格式来,创建一个二维数组,第一层放入第一列中。我们依然可以借助上面的队列来实现。与上面的方法类似,我们还需要再定义一个整型size变量来接受队列的长度,根据队列的长度来选择弹出与进入的操作。

public List<List<Integer>> levelOrder1(TreeNode root){List<List<Integer>> ret = new ArrayList<>();if(root == null) return ret;Queue<TreeNode> queue1 = new LinkedList<TreeNode>();queue1.offer(root);while(! queue1.isEmpty()){List<Integer> curList = new ArrayList<>();int size = queue1.size();while(size != 0){TreeNode cur = queue1.poll();curList.add(cur.val);if(cur.left != null){queue1.offer(cur.left);}if(cur.right != null){queue1.offer(cur.right);}size--;}ret.add(curList);}return ret;}
import java.util.List;public class Test {public static void main(String[] args) {Solution solution = new Solution();TreeNode root = new TreeNode(4,new TreeNode(2),new TreeNode(7));root.left.left = new TreeNode(1);root.left.right = new TreeNode(3);root.right.left = new TreeNode(6);root.right.right = new TreeNode(9);solution.levelOrder(root);List<List<Integer>> result = solution.levelOrder1(root);System.out.println(result);}
}

1.2. 二叉树的最近公共祖先

        如果是上图中第三种情况,那么我们就直接返回root。如果是第一种情况,当root向下遍历时,遇到p、q结点时,直接返回到root(如下图所示)。

        如果是第二种情况,当root遍历到p节点时,5结点返回p的地址,同时我们也可以找到q结点并返回。但还是有一种极端情况,q是孩子节点p的一个子结点。按照上面的思路,直接就返回这个结点。所以这种极端情况可以总结为,只要root遍历到p或者q中一个,直接返回对应的结点。因为p、q都在同一棵子树上,当root去遍历另一棵子树时,会返回null,所以最终结果是p,与p或q在根节点上是类似的。

        完整代码实现:

class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){if(root == null){return root;}if(root == p || root == q){return root;}TreeNode leftT = lowestCommonAncestor(root.left,p,q);TreeNode rightT = lowestCommonAncestor(root.right,p,q);if(leftT != null && rightT != null){//p、q分别在左右子树上return root;}else if(leftT != null){return leftT;} else if (rightT != null) {return rightT;}return null;}
}
public class Test {public static void main(String[] args) {TreeNode root = new TreeNode(3,new TreeNode(5),new TreeNode(1));root.left.left = new TreeNode(6);root.left.right = new TreeNode(2,new TreeNode(7),new TreeNode(4));root.right.left = new TreeNode(0);root.right.right = new TreeNode(8);TreeNode p = root.left;TreeNode q = root.right;Solution solution = new Solution();TreeNode cur = solution.lowestCommonAncestor(root,p,q);System.out.println(cur.val);}
}

        这道题还有另一种做法:如果我们把二叉树里的每一个结点新增加一个前驱域,用来存储父节点的地址,那么这道题的思路就变成了一链表交点的形式来求最近的公共祖先结点。可是定义的TreeNode类里面的成员变量里面没有这个变量。此时可以利用两个栈来存储从root到p、q结点路径上的结点。

        基本思路:只要root不为空,就把结点扔进栈当中。让长度较大的栈先弹出一定的元素,使得两个栈长度相等。两个栈再同时弹出元素,判断两个值是否相等,相等则是最近的公共祖先结点。

        而下面问题又来了,我们该如何求路径上的结点?只要root不等于p或者q,就将该节点放进栈中并继续递归;当root等于p或者q时,就停止。如果在遍历过程中某一个结点既不等于p、q,且左右都为空,那么这个元素就会被弹出。

        完整代码实现:

import java.util.Stack;class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){if(root == null){return false;}stack.push(root);if(root == node){return true;}boolean flag = getPath(root.left,node,stack);if(flag){return true;}flag = getPath(root.right,node,stack);if(flag){return true;}stack.pop();return false;}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){if(root == null){return null;}Stack<TreeNode> stack1 = new Stack<>();Stack<TreeNode> stack2 = new Stack<>();getPath(root,p,stack1);getPath(root,q,stack2);int len1 = stack1.size();int len2 = stack2.size();int len = len1 - len2;if(len < 0){len = Math.abs(len);while(len != 0){stack2.pop();len--;}}else{while(len != 0){stack1.pop();len--;}}//保证两个栈的长度一样while (!stack1.isEmpty() && !stack2.isEmpty()){if(stack1.peek() == stack2.peek()){return stack1.pop();}else{stack1.pop();stack2.pop();}}return null;}
}
public class Test {public static void main(String[] args) {TreeNode root = new TreeNode(3,new TreeNode(5),new TreeNode(1));root.left.left = new TreeNode(6);root.left.right = new TreeNode(2,new TreeNode(7),new TreeNode(4));root.right.left = new TreeNode(0);root.right.right = new TreeNode(8);TreeNode p = root.left;TreeNode q = root.right;Solution solution = new Solution();TreeNode cur = solution.lowestCommonAncestor(root,p,q);System.out.println(cur.val);}
}

1.3. 从前序与中序遍历序列构造二叉树

        基本思路:1.遍历前序遍历的数组,遇到元素之后,在中序遍历数组当中找到该数字;2.该数字的左边就是左树,右边就是右树。上述两步构成一个递归来构造子树。

        我们以中序遍历的数组的第一个元素ibegin,最后一个元素iend之间找到二叉树的根,因为是前序遍历,先有的左树再有的右树,那么左边的区间就会是(9,x) = (ibegin,iend),iend = iroot-1;相反我们去递归右树,ibegin=iroot+1。也就是说,递归根结点创建左树和右树时,还需要知道ibegin和iend的范围。

        我们还需要额外创建一个方法来接受ibegin和iend的参数。创建root,利用buildTreeChild方法递归来创建根结点的左树和右树。可我们不知道中序遍历的数组中根结点的下标,还需要一个方法来查找根结点的下标。

public class Solution {public TreeNode buildTree(int[] preorder, int[] inorder){return buildTreeChild(preorder,0,inorder,0, inorder.length-1);}public TreeNode buildTreeChild(int[] preorder, int prevIndex,int[] inorder, int inbegin, int inend){TreeNode root = new TreeNode(preorder[prevIndex]);int rootIndex = findIndex(inorder,inbegin,inend,preorder[prevIndex]);prevIndex++;root.left = buildTreeChild(preorder,prevIndex,inorder,inbegin,rootIndex-1);root.right = buildTreeChild(preorder,prevIndex,inorder,rootIndex-1,inend);return root;}private int findIndex(int[] inorder,int inbegin,int inend,int key) {for(int i = inbegin; i <= inend; i++) {if(inorder[i] == key) {return i;}}return -1;}
}

        但此时的代码还是有一点逻辑上的问题,就是递归结束的条件是什么?一棵二叉树,总有一棵子树的左右子树都为空。但我们上面的代码没有null。所以要处理一下边界情况:

if(inbegin > inend){return null;
}

        还存在另一个问题,就是局部变量的定义。因为二叉树遍历完左树的时候,最后给根返回0,从0再去遍历右子树。所以我们把prevIndex定义为成员变量。

        完整代码实现: 

class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public int prevIndex;public TreeNode buildTree(int[] preorder, int[] inorder){return buildTreeChild(preorder,inorder,0, inorder.length-1);}public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend){if(inbegin > inend){return null;}TreeNode root = new TreeNode(preorder[prevIndex]);int rootIndex = findIndex(inorder,inbegin,inend,preorder[prevIndex]);prevIndex++;root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);return root;}private int findIndex(int[] inorder,int inbegin,int inend,int key) {for(int i = inbegin; i <= inend; i++) {if(inorder[i] == key) {return i;}}return -1;}
}
public class Test {public static void PrintTreeNode(TreeNode root){if(root == null){return;}System.out.print(root.val+" ");PrintTreeNode(root.left);PrintTreeNode(root.right);}public static void main(String[] args) {Solution soluion = new Solution();int[] preOrder = new int[]{3,9,20,15,7};int[] inOrder = new int[]{9,3,15,20,7};TreeNode root = soluion.buildTree(preOrder,inOrder);PrintTreeNode(root);}
}

1.4. 从中序与后序遍历序列构造二叉树

        与上面一题的思路一样,但后序遍历的顺序是“左子树、右子树、根”,那根结点从后面开始找。并且在创建树的过程中,要先创建右树再创建左树。

class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public int postIndex = 0;public TreeNode buildTree(int[] inorder, int[] postorder){postIndex = postorder.length-1;return buildTreeChild(postorder,inorder,0, inorder.length-1);}public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend){if(inbegin > inend){return null;}TreeNode root = new TreeNode(preorder[postIndex]);int rootIndex = findIndex(inorder,inbegin,inend,preorder[postIndex]);postIndex--;root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);return root;}private int findIndex(int[] inorder,int inbegin,int inend,int key) {for(int i = inbegin; i <= inend; i++) {if(inorder[i] == key) {return i;}}return -1;}
}
public class Test {public static void PrintTreeNode(TreeNode root){if(root == null){return;}PrintTreeNode(root.left);PrintTreeNode(root.right);System.out.print(root.val+" ");}public static void main(String[] args) {Solution solution = new Solution();int[] Inorder = new int[]{9,3,15,20,7};int[] Postorder = new int[]{9,15,7,20,3};TreeNode root = solution.buildTree(Inorder,Postorder);PrintTreeNode(root);}
}

 

1.5. 根据二叉树创建字符串

        通过上图分析:当1的左子树不为空,就用一个(,2的左子树也不为空,也使用一个(,4再往下递归返回null,直接)闭合;2的右子树为null,返回);1的右子树不为空,返回(,3递归返回null,直接)闭合。

        所以我们可以总结下来规律:当子树不为空时,直接加左括号;当root的左树为空,且右树也为空,直接加右括号闭合;当root的左树不为空,右树为空,也加右括号闭合。

    public void tree2strChild(TreeNode root,StringBuilder stringBuilder){if(root == null){return;}stringBuilder.append(root.val);//判断根的左子树if(root.left != null){stringBuilder.append("(");tree2strChild(root.left,stringBuilder);//递归左树stringBuilder.append(")");//左树走完,右括号闭合}else {if(root.right == null){return;//因为4结点走完,返回2结点,这里本身就会加一个")"}else {}}//判断根的右子树if(root.right != null){stringBuilder.append("(");tree2strChild(root.right,stringBuilder);stringBuilder.append(")");}else {}}

        但也存在另一种情况:如果子树的左边为空,右边不为空,就直接加一对小括号,再去递归右树,把4再加进去。再继续往下走,如果root.right为空,正好符合上面2结点的情况:2的左边走完,右边为空,直接return加右括号。所以只要左树为空,右树不为空,就不做任何处理。

        完整代码实现:

class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val;}public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class Solution {public String tree2str(TreeNode root){StringBuilder stringBuilder = new StringBuilder();tree2strChild(root,stringBuilder);return stringBuilder.toString();}public void tree2strChild(TreeNode root,StringBuilder stringBuilder){if(root == null){return;}stringBuilder.append(root.val);//判断根的左子树if(root.left != null){stringBuilder.append("(");tree2strChild(root.left,stringBuilder);//递归左树stringBuilder.append(")");//左树走完,右括号闭合}else {if(root.right == null){return;//因为4结点走完,返回2结点,这里本身就会加一个")"}else {stringBuilder.append("()");}}//判断根的右子树if(root.right != null){stringBuilder.append("(");tree2strChild(root.right,stringBuilder);stringBuilder.append(")");}else {return;}}
}
public class Test {public static void main(String[] args) {Solution solution = new Solution();TreeNode root1 = new TreeNode(1,new TreeNode(2),new TreeNode(3));root1.left.left = new TreeNode(4);TreeNode root2 = new TreeNode(1,new TreeNode(2),new TreeNode(3));root2.left.right = new TreeNode(4);System.out.println(solution.tree2str(root1));System.out.println(solution.tree2str(root2));}
}

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

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

相关文章

ISP 常见流程

1.sensor输出&#xff1a;一般为raw-OBpedestal。加pedestal避免减OB出现负值&#xff0c;同时保证信号超过ADC最小电压阈值&#xff0c;使信号落在ADC正常工作范围。 2. pedestal correction&#xff1a;移除sensor加的基底&#xff0c;确保后续处理信号起点正确。 3. Linea…

Java异常

一&#xff0c;Java异常概述 1.异常概述&#xff1a; 异常&#xff1a;在我们程序运行过程中出现的非正常情况 在开发中&#xff0c;即使我们的代码写的很完善&#xff0c;也有可能由于一些外因&#xff08;用户输入有误&#xff0c;文件被删除&#xff0c;网络问题&#xff…

Linux下的网络通信编程

在不同主机之间&#xff0c;进行进程间的通信。 1解决主机之间硬件的互通 2.解决主机之间软件的互通. 3.IP地址&#xff1a;来区分不同的主机&#xff08;软件地址&#xff09; 4.MAC地址&#xff1a;硬件地址 5.端口号&#xff1a;区分同一主机上的不同应用进程 网络协议…

Metal 学习笔记五:3D变换

在上一章中&#xff0c;您通过在 vertex 函数中计算position&#xff0c;来平移顶点和在屏幕上移动对象。但是&#xff0c;在 3D 空间中&#xff0c;您还想执行更多操作&#xff0c;例如旋转和缩放对象。您还需要一个场景内摄像机&#xff0c;以便您可以在场景中移动。 要移动…

数据集笔记:新加坡LTA MRT 车站出口、路灯 等位置数据集

1 MRT 车站出口 data.gov.sg &#xff08;geojson格式&#xff09; 1.1 kml格式 data.gov.sg 2 路灯 data.govsg ——geojson data.gov.sg——kml 版本 3 道路摄像头数据集 data.gov.sg 4 自行车道网络 data.gov.sg 5 学校区域 data.gov.sg 6 自行车停车架&#xff…

【弹性计算】弹性裸金属服务器和神龙虚拟化(一):功能特点

弹性裸金属服务器和神龙虚拟化&#xff08;一&#xff09;&#xff1a;功能特点 特征一&#xff1a;分钟级交付特征二&#xff1a;兼容 VPC、SLB、RDS 等云平台全业务特征三&#xff1a;兼容虚拟机镜像特征四&#xff1a;云盘启动和数据云盘动态热插拔特征五&#xff1a;虚拟机…

发展中的脑机接口:SSVEP特征提取技术

一、简介 脑机接口&#xff08;BCI&#xff09;是先进的系统&#xff0c;能够通过分析大脑信号与外部设备之间建立通信&#xff0c;帮助有障碍的人与环境互动。BCI通过分析大脑信号&#xff0c;提供了一种非侵入式、高效的方式&#xff0c;让人们与外部设备进行交流。BCI技术越…

EasyRTC:支持任意平台设备的嵌入式WebRTC实时音视频通信SDK解决方案

随着互联网技术的飞速发展&#xff0c;实时音视频通信已成为各行各业数字化转型的核心需求之一。无论是远程办公、在线教育、智慧医疗&#xff0c;还是智能安防、直播互动&#xff0c;用户对低延迟、高可靠、跨平台的音视频通信需求日益增长。 一、WebRTC与WebP2P&#xff1a;实…

为AI聊天工具添加一个知识系统 之127 详细设计之68 编程 核心技术:Cognitive Protocol Language 之2

问题 Q1396、根据我们的讨论&#xff0c;我前面给出的文字表述在用词准确性上以及完整性&#xff08;忽略细节&#xff09; 您觉得有问题吗&#xff1f;有用词错误和 缺项的问题吗 Q1397、请对具体术语的数学定义或工程实现方案进行深度扩展说明 Q1398、 请为全部映射关系提供…

ELK接入SpringBoot【Docker Compose】

安装Docker-Compose curl -L https://github.com/docker/compose/releases/download/1.17.1/docker-compose-uname -s-uname -m -o /usr/local/bin/docker-compose 随便找个地&#xff0c;创建docker-compose.yml文件&#xff0c;把这坨文本复制进去 version: 3 services:el…

基于javaweb的SSM+Maven幼儿园管理系统设计和实现(源码+文档+部署讲解)

技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论…

NAT 代理服务 内网穿透

&#x1f308; 个人主页&#xff1a;Zfox_ &#x1f525; 系列专栏&#xff1a;Linux 目录 一&#xff1a;&#x1f525; NAT 技术背景二&#xff1a;&#x1f525; NAT IP 转换过程三&#xff1a;&#x1f525; NAPT四&#xff1a;&#x1f525; 代理服务器&#x1f98b; 正向…

Apache IoTDB 树表双模型直播回顾(下)

2 月 26 日面向 Apache IoTDB 树表双模型的功能特性、适用场景、建模选择和未来规划&#xff0c;田原同学通过直播进行了全面解答。以下为直播讲稿&#xff08;下&#xff09;&#xff0c;干货满满&#xff0c;建议收藏⬇️⬇️ ⚡️注意&#xff1a; 1. 功能演示部分请直接查看…

LabVIEW中交叉关联算法

交叉关联算法通过统计多通道信号间的相关性&#xff0c;抑制各通道独立的本底噪声&#xff0c;保留共有的有效信号成分。其数学本质为对多个通道信号进行两两相乘并累加&#xff0c;最终通过归一化处理得到降噪后的输出信号。 这个VI演示了如何在LabVIEW中执行信号的互相关分析…

手撸大模型-基础篇 简单线性回归模型预测房价

# NumPy Pandas Matplotlib import numpy as np import matplotlib.pyplot as plt 双特征&#xff0c;矩阵化 1. Min-Max 归一化及其逆操作 1.1 输入数据归一化 def normalize1(sample, data): max_value np.max(data) min_value np.min(data) return (samp…

使用UA-SPEECH和TORGO数据库验证自动构音障碍语音分类方法

使用UA-SPEECH和TORGO数据库验证自动构音障碍语音分类方法 引言 原文:On using the UA-Speech and TORGO databases to validate automatic dysarthric speech classification approaches 构音障碍简介 构音障碍是一种由于脑损伤或神经疾病(如脑瘫、肌萎缩侧索硬化症、帕金森…

React底层原理详解

React中Element&Fiber对象、WorkInProgress双缓存、Reconcile&Render&Commit、第一次挂载过程详解 在面试中介绍React底层原理时&#xff0c;需遵循逻辑清晰、层次分明、重点突出的原则&#xff0c;结合技术深度与实际应用场景。以下是结构化回答模板&#xff1a;…

el-table修改表格颜色

文章目录 一、el-table属性修改表格颜色1.1、header-row-class-name修改表头行颜色1.2、header-row-style修改表头样式1.3、row-class-name修改行颜色 二、el-table-column属性修改表格颜色2.1、class-name修改整列的颜色2.2、label-class-name修改列标题颜色 本文讲解vue修改e…

Graphics View画一个可调速的风机(pyqt)

效果如图&#xff1a; 风机具备调节转速的功能&#xff0c;转速通过扇叶旋转的快慢来区别&#xff0c;共分为四档&#xff0c;其中零档为静止状态&#xff0c;而一、二、三档则依次增加转速。在代码中&#xff0c;BlowerWrapper 类包含了可旋转的扇叶、风机外框以及选项三个主要…

SP脏迹Dirt生成器

常用生成器之一 用于模型表面生成污垢和脏迹 添加一个填充图层 添加黑色遮罩 添加生成器 选择Dirt 调整强度 如果UV有接缝就把Use Triplanar打开