105. Construct Binary Tree from Preorder and Inorder Traversal

Version #2 Stack Iteration[TODO]

二刷 07/2022

Version #3 Recursion with O(N) time - 可以用hashmap记录value和inorder index的map，这样每次不需要iterate去找到root

Time O(N)

Space O(N)

Runtime: 3 ms, faster than 88.47% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

Memory Usage: 44.4 MB, less than 47.16% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        Map<Integer, Integer> inMap = new HashMap<>();

        // key-value of the node, value-index of that value in the inorder array

        for (int i = 0; i < inorder.length; i++) {

            inMap.put(inorder[i], i);

        }

        return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);

    }

    

    private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {

        if (preStart > preEnd || preStart >= preorder.length) {

            return null;

        }

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

        if (preStart == preEnd) {

            return root;

        }

        int inIndex = inMap.get(root.val);

        // [inStart, inIndex - 1] root [inIndex + 1, inEnd]

        // root [preStart + 1, preStart + inIndex - inStart] [preStart + inIndex - inStart + 1, preEnd]

        root.left = buildTreeHelper(preorder, preStart + 1, preStart + inIndex - inStart, inorder, inStart, inIndex - 1, inMap);

        root.right = buildTreeHelper(preorder, preStart + inIndex - inStart + 1, preEnd, inorder, inIndex + 1, inEnd, inMap);

        return root;

    }

}

Version #1 Recursion

写了一个bug就是root.left的preStart parameter应该是preStart + 1因为排除了第一个root的值

另外一个就是要检查preStart是不是出界

Time O(Nh) -> O(N^2) worst

Space O(1)

Runtime: 4 ms, faster than 64.48% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

Memory Usage: 44.6 MB, less than 40.80% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        // preorder: root -> left -> right

        // inorder: left -> root -> right

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

    }

    

    private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {

        if (preStart > preEnd || preStart >= preorder.length) {

            return null;

        }

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

        if (preStart == preEnd) {

            return root;

        }

        int i = 0;

        for (i = inStart; i <= inEnd; i++) {

            if (inorder[i] == root.val) {

                break;

            }

        }

        // preorder preorder[0], pre

        // left part [inStart, i - 1], right part [i + 1, inEnd]

        root.left = buildTreeHelper(preorder, preStart + 1, preStart + (i - inStart), inorder, inStart, i - 1);

        root.right = buildTreeHelper(preorder, preStart + (i + 1 - inStart), preEnd, inorder, i + 1, inEnd);

        return root;

    }

}

一刷
Version #1 Recursion
Preorder的第一个index是root
在inorder里面找到root可以把当前layer parse为left subtree & right subtree
然后到下一层进行recursion construction

难点在于需要的参数
第一个index是必须的 -> preStart
根据preStart之后， 在inorder的给定范围内搜索这个值，所以需要inStart和inEnd
搜索到之后确定的是inIndex
这时候left subtree 和right subtree的length都可以确定了，所以不再需要其他参数

Base case写的比较草率。。。竟然也过了
这里的根据是不要出现死循环或者出界，没有想更多
Space O(1) 没有extra data structure
Time O(nlogn)我猜的 每一层是O(n), 一共大概是logn层


65.22 %

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) return null;
        //TODO
        return buildTree(preorder, 0, inorder, 0, inorder.length - 1);
    }
   
    /*
          inStart      inIndex   inEnd
    inorder  4    1  3     5       2
   
            preStart  leftLength rightLength
    preorder   5       1  4  3        2
         root[5]
   left[4 1 3]   right[2]
   
    */
    private TreeNode buildTree(int[] preorder, int preStart, int[] inorder, int inStart, int inEnd) {
        if (inStart > inEnd || inEnd >= inorder.length) return null;
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) inIndex = i;
        }
        root.left = buildTree(preorder, preStart + 1, inorder, inStart, inIndex - 1);
        root.right = buildTree(preorder, preStart + 1 + (inIndex - inStart), inorder, inIndex + 1, inEnd);
        return root;
    }
}