LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal
2022/4/9 23:21:17
本文主要是介绍LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal (根据前序和后序遍历构造二叉树)
题目
链接
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
问题描述
给定两个整数数组,preorder 和 postorder ,其中 preorder 是一个具有 无重复 值的二叉树的前序遍历,postorder 是同一棵树的后序遍历,重构并返回二叉树。
如果存在多个答案,您可以返回其中 任何 一个。
示例
输入:preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出:[1,2,3,4,5,6,7]
提示
1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
preorder 中所有值都 不同
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
postorder 中所有值都 不同
保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历
思路
由于这无法确定唯一的一颗二叉树,所以我们假设排除根节点后,左边第一个节点是左子树的根节点,然后进行递归操作。
复杂度分析
时间复杂度 O(n^2) 空间复杂度 O(n^2)
代码
Java
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) { int n = postorder.length; if (n == 0) { return null; } TreeNode root = build(preorder, 0, n - 1, postorder, 0, n - 1); return root; } public TreeNode build(int[] preorder, int pres, int pree, int[] postorder, int posts, int poste) { if (pres > pree) { return null; } if (pres == pree) { return new TreeNode(preorder[pres]); } int rootval = preorder[pres]; int leftval = preorder[pres + 1]; int index = -1; for (int i = posts; i <= poste; i++) { if (postorder[i] == leftval) { index = i; break; } } int size = index - posts + 1; TreeNode root = new TreeNode(rootval); root.left = build(preorder, pres + 1, pres + size, postorder, posts, index); root.right = build(preorder, pres + size + 1, pree, postorder, index + 1, poste - 1); return root; }
这篇关于LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享