1. Description

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

2. Runtime Distribution

3. Submission Details

5. Code

private int preId;
private int inId;
public TreeNode buildTree(int[] preorder, int[] inorder)
{
    preId = 0;
    inId = 0;
    return buildTree(preorder, inorder, null);
}

private TreeNode buildTree(int[] preorder, int[] inorder, TreeNode father)
{
    if (preId >= preorder.length) {
        return null;
    }

    TreeNode root = new TreeNode(preorder[preId++]);

    if (inorder[inId] != root.val) {
        root.left = buildTree(preorder, inorder, root);
    }

    inId++;

    if (father == null || inorder[inId] != father.val) {
        root.right = buildTree(preorder, inorder, father);
    }

    return root;
}

public TreeNode buildTree(int[] preorder, int[] inorder)
{
    if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
        return null;
    }

    return build(preorder, 0, inorder, 0, inorder.length - 1);
}

public TreeNode build(int[] preorder, int pStart, int[] inorder, int iStart, int iEnd)
{
    if (pStart >= preorder.length || iStart > iEnd) {
        return null;
    }
    for (int i = iEnd; i >= iStart; i--) {
        if (inorder[i] == preorder[pStart]) {
            TreeNode root = new TreeNode(preorder[pStart]);
            root.left = build(preorder, pStart + 1, inorder, iStart, i - 1);
            root.right = build(preorder, i - iStart + pStart + 1, inorder, i + 1, iEnd);
            return root;
        }
    }
    return null;
}

6.Test

public class LeetCode0105 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    private int preId;
    private int inId;
    public TreeNode buildTree(int[] preorder, int[] inorder)
    {
        preId = 0;
        inId = 0;
        return buildTree(preorder, inorder, null);
    }

    private TreeNode buildTree(int[] preorder, int[] inorder, TreeNode father)
    {
        if (preId >= preorder.length) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preId++]);

        if (inorder[inId] != root.val) {
            root.left = buildTree(preorder, inorder, root);
        }

        inId++;

        if (father == null || inorder[inId] != father.val) {
            root.right = buildTree(preorder, inorder, father);
        }

        return root;
    }
}

public class LeetCode0105 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder)
    {
        if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
            return null;
        }

        return build(preorder, 0, inorder, 0, inorder.length - 1);
    }

    public TreeNode build(int[] preorder, int pStart, int[] inorder, int iStart, int iEnd)
    {
        if (pStart >= preorder.length || iStart > iEnd) {
            return null;
        }
        for (int i = iEnd; i >= iStart; i--) {
            if (inorder[i] == preorder[pStart]) {
                TreeNode root = new TreeNode(preorder[pStart]);
                root.left = build(preorder, pStart + 1, inorder, iStart, i - 1);
                root.right = build(preorder, i - iStart + pStart + 1, inorder, i + 1, iEnd);
                return root;
            }
        }
        return null;
    }
}