java实现根据先序遍历和中序遍历结果复原二叉树(剑指offer)
2021/11/22 17:10:11
本文主要是介绍java实现根据先序遍历和中序遍历结果复原二叉树(剑指offer),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
思路
前序遍历序列为根左右顺序,中序遍历序列为左根右。
- 首先根据前序遍历序列确定根节点,然后在中序遍历序列寻找根节点位置,考虑到当前序列在中序遍历序列的开始位置从而在中序遍历序列中能够确定左子树的长度。
- 依据左子树长度以及当前序列在前序遍历序列的开始位置,确定左子树;
- 进而考虑上当前序列在前序遍历序列的结束位置能够确定右子树。由于每次流程相同,考虑使用递归,完成每一次左右子树的确定。
考虑代码具体实现
- 建立HashMap存储中序遍历序列中<值>-<索引>,便于确定当前根节点在中序遍历序列中的位置
- 建立一个递归函数,递归函数每次处理当前的前序遍历序列和中序遍历序列。
参数,
int pre[]前序遍历序列
preL 当前处理的序列在pre[]中的开始位置
preR 当前处理的序列在pre[]中的结束位置
inL 当前处理的序列在in[](中序序列)的开始位置
- 递归的结束条件:preL > preR
代码实现
import java.util.*; public class Solution { private HashMap<Integer,Integer> indexForInOrders = new HashMap<>(); public TreeNode reConstructBinaryTree(int[] pre, int[] in) { for (int i = 0; i < in.length; i++) indexForInOrders.put(in[i], i); return reConstructBinaryTree(pre, 0, pre.length-1 , 0); } private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) { if (preL > preR) return null; TreeNode root = new TreeNode(pre[preL]); int index = indexForInOrders.get(root.val); int leftTreeSize = index-inL; root.left = reConstructBinaryTree(pre,preL+1,preL+leftTreeSize,inL); root.right = reConstructBinaryTree(pre,preL+leftTreeSize+1,preR,inL+leftTreeSize+1); return root; } }
这篇关于java实现根据先序遍历和中序遍历结果复原二叉树(剑指offer)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南