BiruLyu
8/3/2017 - 5:58 AM

105. Construct Binary Tree from Preorder and Inorder Traversal(#).java

``````/**
* 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 || preorder.length == 0
|| inorder == null || inorder.length == 0) return null;

Map<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, map, 0);
}

private TreeNode helper(int[] preorder, int pl, int pr, Map<Integer, Integer> map, int il) {
if (pl > pr) return null;

TreeNode node = new TreeNode(preorder[pl]);
if (pl == pr) {
return node;
}

int i = map.get(preorder[pl]);
int len = i - il;
node.left = helper(preorder, pl + 1, pl + len, map, il);
node.right = helper(preorder, pl + len + 1, pr, map, i + 1);
return node;
}
}``````
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int pre = 0;
int in = 0;

public TreeNode buildTree(int[] preorder, int[] inorder) {
return builder(preorder, inorder, Integer.MAX_VALUE);
}

private TreeNode builder(int[] preorder, int[] inorder, int border) {
if (in >= inorder.length || inorder[in] == border) { return null; }

TreeNode root = new TreeNode(preorder[pre]);
pre++;
root.left = builder(preorder, inorder, root.val);
in++;
root.right = builder(preorder, inorder, border);

return root;
}
}``````
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private TreeNode helper(int[] preorder, int[] inorder, int rootIdx, int start, int end) {
if (rootIdx > preorder.length - 1 || start > end) return null;
TreeNode root = new TreeNode(preorder[rootIdx]);
int inIdx = 0;
for (int i = start; i <= end; i++) {
if(inorder[i] == root.val) {
inIdx = i;
}
}
root.left = helper(preorder, inorder, rootIdx + 1, start, inIdx - 1);
root.right = helper(preorder, inorder, rootIdx + inIdx - start + 1, inIdx + 1, end);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(preorder, inorder, 0, 0, preorder.length - 1);
}
}``````