- 浏览: 173613 次
- 性别:
- 来自: 济南
文章分类
最新评论
iven preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
给定一棵树的中序遍历和前序遍历,构造出这棵树。我们可以通过前序遍历序列的第一个元素判断出每个子树的根节点,然后在中序遍历序列找到这个根节点,假设这个根结点在i位置,那么在inorder[i]左边的就是左子树的元素,在inorder[i]右边的就是右子树的元素。用递归来完成。代码如下:
上面的代码每次递归都要在中序遍历序列中找当前的根节点,如果我们用一个哈希表来存储中序遍历序列的值和下标,那么每次查找的时间就可以缩减为O(1),这样大大优化的算法的效率。代码如下:
Note:
You may assume that duplicates do not exist in the tree.
给定一棵树的中序遍历和前序遍历,构造出这棵树。我们可以通过前序遍历序列的第一个元素判断出每个子树的根节点,然后在中序遍历序列找到这个根节点,假设这个根结点在i位置,那么在inorder[i]左边的就是左子树的元素,在inorder[i]右边的就是右子树的元素。用递归来完成。代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder == null || inorder == null || preorder.length == 0) return null; TreeNode root = new TreeNode(preorder[0]); int i; for(i = 0; i < inorder.length; i++) { if(preorder[0] == inorder[i]) break; } root.left = buildTree(Arrays.copyOfRange(preorder, 1, i + 1), Arrays.copyOfRange(inorder, 0, i)); root.right = buildTree(Arrays.copyOfRange(preorder, i + 1, preorder.length), Arrays.copyOfRange(inorder, i + 1, inorder.length)); return root; } }
上面的代码每次递归都要在中序遍历序列中找当前的根节点,如果我们用一个哈希表来存储中序遍历序列的值和下标,那么每次查找的时间就可以缩减为O(1),这样大大优化的算法的效率。代码如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder == null || inorder == null || preorder.length == 0) return null; HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); for(int i = 0; i < inorder.length; i++) hm.put(inorder[i], i); return getTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, hm); } public TreeNode getTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, HashMap<Integer, Integer> hm) { if(preStart > preEnd || inStart > inEnd) return null; TreeNode root = new TreeNode(preorder[preStart]); int position = hm.get(root.val); int leftNums = position - inStart; root.left = getTree(preorder, preStart + 1, preStart + leftNums, inorder, inStart, position - 1, hm); root.right = getTree(preorder, preStart + leftNums + 1, preEnd, inorder, position + 1, inEnd, hm); return root; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 226You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 342Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 334Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 451Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 512Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 430Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 620Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 428The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 519Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 533Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 861Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 555Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 601Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 764Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 736You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 629For a undirected graph with tre ...
相关推荐
105.construct_binary_tree_from_preorder_and_inorder_traversal从前序
Construct Binary Tree from Inorder and Postorder Traversa.根据先序后续构建二叉树
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...
Inorder Traversal 用两个栈实现队列 232. Implement Queue using Stacks 旋转数组的最小数字 153. Find Minimum in Rotated Sorted Array 斐波那契数列 509. Fibonacci Number 跳台阶 70. Climbing Stairs 变态跳...
421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an-array.cpp) [Python](./Python/...
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
Construct Optimal Binary Search Tree by Using Greedy Algorithm
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 ...
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 ...
二叉树的实现代码 /*LinkTree.h*/ typedef int DataType; //这样定义意味着节点中能放一个整数,但如果是非叶子节点则可以解读为对应的操作符的ascii ...void inOrder( BinTree t); //travel in order
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 2 题目描述 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序...
concerning 345 burglars and 310 violent offenders in Nottinghamshire, England. The most important observable features of offenders were sex, ethnicity, age, height, build, hair color, hair length, and...
The frequency's must be listed, in order, from largest (at the top) to smallest (at the bottom) Then, using the Huffman algorithm, construct the optimal prefix binary code for the table. The Huffman ...
内含大量实例,来自多个知名算法测试平台的题目,还有讲解。
language testing 权威刊物文章 可供语言测试与学习者使用。
A Basic Tool to Construct Basic Pourbaix and Tafe
The methodology used to construct tree structured rules is the focus of this monograph. Unlike many other statistical procedures, which moved from pencil and paper to calculators, this text's use of ...