通过先序和中序数组生成后序数组(Java)
2022/1/22 21:06:04
本文主要是介绍通过先序和中序数组生成后序数组(Java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请轻击http://www.captainbed.net
package live.every.day.DataStructure.Tree.BinaryTree; import java.util.Arrays; import java.util.HashMap; /** * 题目: * 通过先序和中序数组生成后序数组。 * * 思路: * 先设置后序数组最右边的值,再根据右子树和左子树的划分,从右到左依次设置好后序数组的全部位置。 * * @author Created by LiveEveryDay */ public class GetPostArrayByPreOrderInOrder { public static int[] getPostArray(int[] pre, int[] in) { if (pre == null || in == null) { return null; } int len = pre.length; int[] post = new int[len]; HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < len; i++) { map.put(in[i], i); } setPos(pre, 0, len - 1, in, 0, len - 1, post, len - 1, map); return post; } private static int setPos(int[] p, int pi, int pj, int[] n, int ni, int nj, int[] s, int si, HashMap<Integer, Integer> map) { if (pi > pj) { return si; } s[si--] = p[pi]; int i = map.get(p[pi]); si = setPos(p, pj - nj + i + 1, pj, n, i + 1, nj, s, si, map); return setPos(p, pi + 1, pi + i - ni, n, ni, i - 1, s, si, map); } public static void main(String[] args) { int[] pre = {1, 2, 4, 5, 8, 9, 3, 6, 7}; int[] in = {4, 2, 8, 5, 9, 1, 6, 3, 7}; int[] post = getPostArray(pre, in); System.out.printf("The post array is: %s", Arrays.toString(post)); } } // ------ Output ------ /* The post array is: [4, 8, 9, 5, 2, 6, 7, 3, 1] */
这篇关于通过先序和中序数组生成后序数组(Java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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学习:新手快速入门指南