当前位置:网站首页>如何根据“前序遍历,中序遍历”,“中序遍历,后序遍历”构建按二叉树
如何根据“前序遍历,中序遍历”,“中序遍历,后序遍历”构建按二叉树
2022-08-04 21:10:00 【陈亦康】
如何根据前序遍历和中序遍历,或者中序遍历和后序遍历创建二叉树?大致思路如下文章;
分析:
代码如下:
/**
* 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 int preIndex;
public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegan, int inEnd){
//如果ib > ie说明递归终止
if(inBegan > inEnd){
return null;
}
//创建根节点
TreeNode root = new TreeNode(preorder[preIndex]);
//在中序遍历中找到对应的根节点下标
int InorderIndex = fundInorderIndex(inorder, preorder[preIndex], inBegan, inEnd);
//前序遍历中的下标继续往后遍历
preIndex++;
//通过递归继续创建左子树和右子树
root.left = buildTreeChild(preorder, inorder, inBegan, InorderIndex - 1);
root.right = buildTreeChild(preorder, inorder, InorderIndex + 1, inEnd);
//最后返回根结点即可
return root;
}
public int fundInorderIndex(int[] inorder, int val, int inBegan, int inEnd){
for(int i = inBegan; i <= inEnd; i++){
if(inorder[i] == val){
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
}
}
分析:
和前序与中序遍历的思路一样,但是注意的是,后序遍历中是从后向前找根结点,因此,当你写出后序遍历的顺序的时候,会发现需要先创建右子树,再创建左子树。
代码如下:
/**
* 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 int preIndex;
public TreeNode buildTreeChild(int[] postorder, int[] inorder, int inBegan, int inEnd){
//如果ib > ie说明递归终止
if(inBegan > inEnd){
return null;
}
//创建根节点
TreeNode root = new TreeNode(postorder[preIndex]);
//在中序遍历中找到对应的根节点下标
int InorderIndex = fundInorderIndex(inorder, postorder[preIndex], inBegan, inEnd);
//前序遍历中的下标继续往后遍历
preIndex--;
//这里要注意,先构建左树再构建右树!
root.right = buildTreeChild(postorder, inorder, InorderIndex + 1, inEnd);
root.left = buildTreeChild(postorder, inorder, inBegan, InorderIndex - 1);
//最后返回根结点即可
return root;
}
public int fundInorderIndex(int[] inorder, int val, int inBegan, int inEnd){
for(int i = inBegan; i <= inEnd; i++){
if(inorder[i] == val){
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
preIndex = postorder.length - 1;
return buildTreeChild(postorder, inorder, 0, inorder.length - 1);
}
}
边栏推荐
猜你喜欢
随机推荐
STM32MP157A驱动开发 | 01- 板载LED作为系统心跳指示灯
Android 面试——如何写一个又好又快的日志库?
C#之app.config、exe.config和vshost.exe.config作用区别
moke、动态图片资源打包显示
dotnet 启动 JIT 多核心编译提升启动性能
经验分享|盘点企业进行知识管理时的困惑类型
【Programming Ideas】
机器学习_02
Chapter7 : Network-Driven Drug Discovery
LINQ to SQL (Group By/Having/Count/Sum/Min/Max/Avg操作符)
Common methods of js's new Function()
Red team kill-free development practice of simulated confrontation
使用堡塔应用管理器配置laravel队列方法
两种白名单限流方案(redis lua限流,guava方案)
如何最简单、通俗地理解爬虫的Scrapy框架?
Pinduoduo open platform order information query interface [pdd.order.basic.list.get order basic information list query interface (according to transaction time)] code docking tutorial
数字IC设计中基本运算的粗略的延时估计
【一起学Rust | 进阶篇 | Service Manager库】Rust专用跨平台服务管理库
无代码平台字段设置:基础设置入门教程
3、IO流之字节流和字符流