首页 > itarticle > [leetcode] problem 105 – construct binary tree from preorder and inorder traversal

[leetcode] problem 105 – construct binary tree from preorder and inorder traversal

admin 11月 13, 2020 0

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:

Code

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

public TreeNode buildTree(int[] preorder, int[] inorder) {
    return helper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}

private TreeNode helper(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd)
            return null;

    int i = inStart;

    for (; i <= inEnd; i++) {
            if (inorder[i] == preorder[preStart])
                    break;
    }

    TreeNode root = new TreeNode(preorder[preStart]);
    root.left = helper(preorder, inorder, preStart + 1, preStart + i - inStart, inStart, i - 1);
    root.right = helper(preorder, inorder, preStart + i - inStart + 1, preEnd, i + 1, inEnd);

    return root;
}