105. Construct Binary Tree from Preorder and Inorder Traversal — Medium

前往題目

之前寫過的文章

想法

• 觀察inorder和preorder的規律

思路

1. preorder的第一項一定是root，這是它的特性
2. inorder的每個父節點，左邊一定是left subtree，右邊一定是right subtree
3. 把inorder的val->index資訊存下來
4. builder function每個循環都取得當前值，以及取得mid的index
5. 根據mid來呼叫builder進一步建造左和右子樹

Code

class Solution {
    // num -> index
    Map<Integer, Integer> inorderMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length < 1 || inorder.length < 1) return null;

        for (int i = 0; i < inorder.length; ++i) {
            inorderMap.put(inorder[i], i);
        }
        return build(preorder, 0, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int preorderIndex, int low, int high) {
        // Base case
        if (preorderIndex > preorder.length - 1 || low > high) {
            return null;
        }
        // 當前值
        int currentVal = preorder[preorderIndex];
        TreeNode n = new TreeNode(currentVal); // Build tree
        // 取得父節點
        int mid = inorderMap.get(currentVal); // Obtain mid index

        n.left = build(preorder, preorderIndex + 1, low, mid - 1);

        n.right = build(preorder, preorderIndex + (mid - low + 1), mid + 1, high);

        return n;
    }
}