PattySung

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7] Example 2:

Input: inorder = [-1], postorder = [-1] Output: [-1]

<解題>

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return helper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1, map);
    }
    private TreeNode helper(int[] inorder,
                            int[] postorder,
                            int inStart,
                            int inEnd,
                            int postStart,
                            int postEnd,
                            HashMap<Integer, Integer> map){
        if(inStart > inEnd || postStart < 0) return null;
        TreeNode root = new TreeNode(postorder[postEnd]);

        int rootIndex = map.get(postorder[postEnd]);

        root.left = helper(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + rootIndex - inStart - 1, map);

        root.right = helper(inorder, postorder, rootIndex + 1, inEnd, postStart + rootIndex - inStart, postEnd - 1, map);
        
        
        return root;
    }
}

Time: O(n) Space: O(n)

Leetcode-105. Construct Binary Tree from Preorder and Inorder Traversal

<解題>