105. Construct Binary Tree from Preorder and Inorder Traversal(由先序遍历和中序遍历构建二叉树)
题目描述
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
方法思路
Approach1:
由中序遍历和先序遍历确定二叉树
0.确定递归返回的临界条件。
if(start > end) return null;
1.根据先序遍历确定根结点:TreeNode root = new TreeNode(preorder[preIndex++]);因为先序遍历的特 性,可将preIndex设置为全局变量,很方便,而后序遍历与中序遍历的组合就无法使用全局变量了 。
2.在中序遍历的数组中确定根结点的索引:int index = map.get(root.val);
3.确定左子树与右子树的范围。
root.left = btHelper(preorder,map,start,index-1);
root.right = btHelper(preorder,map,index+1,end);
4.return root;
class Solution {
//Runtime: 2 ms, faster than 97.75%
//Memory Usage: 37.2 MB, less than 86.50%
int preIndex = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || preorder.length == 0) return null;
Map<Integer,Integer> map = new HashMap();
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i],i);
}
return btHelper(preorder,map,0, inorder.length-1);
}
private TreeNode btHelper(int[] preorder, Map<Integer,Integer> map, int start, int end){
if(start > end) return null;
//由先序遍历数组可以很容易的得到根结点的值
TreeNode root = new TreeNode(preorder[preIndex++]);
//index 是当前子树的根结点的索引,由此可以得到左右子树的索引范围,从而进行递归
int index = map.get(root.val);
root.left = btHelper(preorder,map,start,index-1);
root.right = btHelper(preorder,map,index+1,end);
return root;
}
}
Approach2:
更加一般性的方法
class Solution {
//Runtime: 7 ms, faster than 53.85%
//Memory Usage: 37.2 MB, less than 82.21%
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(inorder, preorder, 0, 0, inorder.length-1);
}
public TreeNode build(int[] inorder, int[] preorder, int pre_start, int in_start, int in_end) {
if (pre_start > preorder.length-1 || in_start > in_end) return null;
TreeNode root = new TreeNode(preorder[pre_start]);
int index = 0;
for (int i = in_start; i <= in_end; i++)
if (inorder[i] == root.val)
index = i;
root.left =
build(inorder, preorder, pre_start + 1, in_start, index-1);
root.right =
build(inorder, preorder, pre_start + (index - in_start + 1), index + 1, in_end);
return root;
}
}