Comment on page

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.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7

代码

Approach 1: Recursion

inorder数组用来获取反向索引
preorder数组用来递归
Time complexity : O(N) & Space complexity : O(N), since we store the entire tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int preIndex = 0;
HashMap<Integer, Integer> map = new HashMap();
int[] preorder;
int[] inorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
int len = preorder.length;
this.preorder = preorder;
this.inorder = inorder;
for (int i = 0; i < len; i++) {
map.put(inorder[i], i);
}
return dfs(0, len - 1);
}
private TreeNode dfs(int start, int end) {
if (start > end) return null;
int rootVal = preorder[preIndex];
TreeNode root = new TreeNode(rootVal);
int index = map.get(rootVal);
preIndex++;
root.left = dfs(start, index - 1);
root.right = dfs(index + 1, end);
return root;
}
}