105. Construct Binary Tree from Preorder and Inorder Traversal

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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

Code

654

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }

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

    private TreeNode helper(int[] preorder,
                            int[] inorder,
                            int preStart,
                            int inStart,
                            int inEnd,
                            HashMap<Integer, Integer> map){

        if(preStart >= preorder.length || inStart > inEnd) return null;

        TreeNode root = new TreeNode(preorder[preStart]);

        int rootIndex = map.get(preorder[preStart]);

        root.left = helper(preorder, inorder, preStart + 1, inStart, rootIndex - 1, map);
        root.right = helper(preorder, inorder, preStart + rootIndex - inStart + 1, rootIndex + 1, inEnd, map);

        return root;
    }
}