Construct Binary Tree from Preorder and Inorder Traversal

Question

Given a binary search tree, write a function kthSmallest to find Given preorder and inorder traversal of a tree, construct the binary tree.

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

Solution

這題我覺得算是滿經典的題目，雖然我第二次寫還是卡住。第二次寫有記得一個概念是 inorder 找到跟 preorder 提供的 node 時，左邊是 left, 右邊是 right。但沒有太清楚知道 preorder 是幹嘛，還有整個的 recursion 該怎麼寫。

1. preorder 其實給我們的是 root，他會照著順序往下
2. inorder 給的是一種相對關係。相對於當前這個 root, 在 array 左邊的都是 left, 右邊都是 right

需要特別注意的是，在找 root.left 跟 root.right 時候 preStart 該怎麼取。

另外，follow up 是做 inorder 跟 postorder，同樣概念，但 preStart 的取法也是得特別注意

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

    public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart > preorder.length - 1 || inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preStart]);
        int inIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
            }
        }

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

        return root;
    }
}