leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal
z
 2019-04-09 10:36:27  

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

1
2
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import utils.TreeNode;

import java.util.Arrays;

public class ConstructBinaryTreefromPreorderandInorderTraversal {
  public TreeNode buildTree(int[] preorder, int[] inorder) {
    return helper(preorder, inorder, 0, preorder.length, 0, inorder.length);
  }
  public TreeNode helper(int[] preorder, int[] inorder, int prel, int prer, int inl ,int inr) {
    if (inl == inr) return new TreeNode(inorder[inl]);
    TreeNode root = new TreeNode(preorder[prel]);
    int i = inl;
    for (i = inl; i<inr; i++) {
      if (inorder[i] == root.val) {
        break;
      }
    }
    root.left = helper(preorder, inorder, prel+1,prel+(i-inl), inl, i-1);
    root.right = helper(preorder, inorder, prel+(i-inl)+1, prer, i+1, inr);
    return root;
  }
}