原题链接:http://oj.leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/这道题是树中比较有难度的题目,需要根据先序遍历和中序遍历来构造出树来。这道题看似毫无头绪,其实梳理一下还是有章可循的。下面我们就用一个例子来解释如何构造出树。假设树的先序遍历是12453687,中序遍历是42516837。这里最重要的一点就是先序遍历可以提供根的所在,而根据中序遍历的性质知道根的所在就可以将序列分为左右子树。比如上述例子,我们知道1是根,所以根据中序遍历的结果425是左子树,而6837就是右子树。接下来根据切出来的左右子树的长度又可以在先序便利中确定左右子树对应的子序列(先序遍历也是先左子树后右子树)。根据这个流程,左子树的先序遍历和中序遍历分别是245和425,右子树的先序遍历和中序遍历则是3687和6837,我们重复以上方法,可以继续找到根和左右子树,直到剩下一个元素。可以看出这是一个比较明显的递归过程,对于寻找根所对应的下标,我们可以先建立一个HashMap,以免后面需要进行线行搜索,这样每次递归中就只需要常量操作就可以完成对根的确定和左右子树的分割。算法最终相当于一次树的遍历,每个结点只会被访问一次,所以时间复杂度是O(n)。而空间我们需要建立一个map来存储元素到下标的映射,所以是O(n)。代码如下:public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null || inorder==null)
return null;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i=0;i<inorder.length;i++)
{
map.put(inorder[i],i);
}
return helper(preorder,0,preorder.length-1,inorder,0,inorder.length-1, map);
}
private TreeNode helper(int[] preorder, int preL, int preR, int[] inorder, int inL, int inR, HashMap<Integer, Integer> map)
{
if(preL>preR || inL>inR)
return null;
TreeNode root = new TreeNode(preorder[preL]);
int index = map.get(root.val);
root.left = helper(preorder, preL+1, index-inL+preL, inorder, inL, index-1, map);
root.right = helper(preorder, preL+index-inL+1, preR, inorder, index+1, inR,map);
return root;
}
可以看出上面实现结果还是非常接近于一次树的遍历的,只是我们是以一个构造树的形式,在遍历中把树创建出来。这种题目算是树中的难题了,不过理清思路,其实也不过如此哈~
分享到:
相关推荐
Construct Binary Tree from Preorder and Inorder Traversal 根据先序,中序建立二叉树
105.construct_binary_tree_from_preorder_and_inorder_traversal从前序
Construct Binary Tree from Inorder and Postorder Traversa.根据先序后续构建二叉树
105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造二叉树) 106.construct-binary-tree-from-inorder-and-postorder-traversal (从中序与后序遍历序列构造二叉树) 112.path-...
[105_construct-binary-tree-from-preorder-and-inorder-traversal.cpp] [106_construct-binary-tree-from-inorder-and-postorder-traversal.cpp] [107_binary-tree-level-order-traversal-ii.cpp] [108_convert-...
construct-binary-tree-from-preorder-and-inorder-traversal 无官方题解 106 construct-binary-tree-from-inorder-and-postorder-traversal 无官方题解 116 populating-next-right-pointers-in-eac
Inorder Traversal 用两个栈实现队列 232. Implement Queue using Stacks 旋转数组的最小数字 153. Find Minimum in Rotated Sorted Array 斐波那契数列 509. Fibonacci Number 跳台阶 70. Climbing Stairs 变态跳...
201 | [Bitwise AND of Numbers Range](https://leetcode.com/problems/bitwise-and-of-numbers-range/) | [C++](./C++/bitwise-and-of-numbers-range.cpp) [Python](./Python/bitwise-and-of-numbers-range.py) | _...
Construct Binary Tree from Preorder and Inorder Traversal Construct Binary Tree from Inorder and Postorder Traversal 二叉查找树 Unique Binary Search Trees Unique Binary Search Trees II Validate Binary...
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 2 题目描述 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序...
leetcode 不会LeetCode_492--构造矩形 对于 Web 开发人员来说,了解如何设计网页的大小非常重要。 因此,给定一个特定的矩形网页区域,您现在的工作是设计一个矩形网页,其长度 L 和宽度 W 满足以下要求: 您设计的...
leetcode 316 LeetCode Summary Exclusive Time of Functions: 栈 Friend Circles:DFS Print Binary Tree:二叉树 Maximal Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:...
to construct binary codes for users and items such that the preference of users over items can be accurately preserved by the Hamming distance between their respective binary codes. By using two loss ...
Construct Optimal Binary Search Tree by Using Greedy Algorithm
poj与leetcode 自述文件 介绍 本repo由鞠承佑、钟恺健、王少泽创建。 它在帐户SuanFaRuoji(算法弱鸡)下...└──889_construct_binary_tree_from_preorder_and_postorder_traversal └──zkj_python.py 我们的任务
1400. 构造 K 个回文字符串哈希表(碰巧跟题解思路一模一样)function canConstruct(s: string, k: number): bo
No prior experience is required.Game Development with Construct 2 teaches you to create 12 different game projects from a variety of genres, including car racing and tower defense to platformer and ...
//type of binary tree struct Node /* type of node*/ { DataType info; BinTree llink; BinTree rlink; }; BinTree createEmptyTree( void ); BinTree consBintree (DataType val, BinTree left, ...
这就是我在LeetCode中解决的所有问题。 解决问题后,我将更新此存储库。 此仓库中的所有解决方案都是用Java编写的。 您可以关注我的仓库,阅读我的代码,并为我提供更好的解决方案。 另外,欢迎指出我的解决方案中的...
leetcode安卓 construct_android_dev_skill_tree 构建android知识体系 算法数据结构 Java进阶 Kotlin 性能优化 -