LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal

這題類似給Preoder 跟 Inorder的順序 請你把整棵樹給建立出來。

蠻有趣而且我覺得不算簡單。

首先這邊有一個很重要的觀察就是

來源在這https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34579/Python-short-recursive-solution.

Preorder第一個一定是整棵樹的根。然後接下來分成左子樹根右子樹

然後在Inorder裡面找到這個根的時候，等於這個數字的左邊是屬於左子樹，右邊是右邊是右子樹。

所以可以寫出一個遞迴

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; // Index of current root in inorder
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == root.val) {
            inIndex = i;
        }
    }
    root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
    root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
    return root;
}

透過這樣的方法就可以建立出來。

有一個比較簡潔的寫法 可是腦袋要夠清楚

var buildTree = function(preorder, inorder) {
    p = i = 0
    build = function(stop) {
        if (inorder[i] != stop) {
            var root = new TreeNode(preorder[p++])
            root.left = build(root.val)
            i++
            root.right = build(stop)
            return root
        }
        return null
    }
    return build()
};

因為左邊的子樹會先被建立完，所以用 i 當Iterator。

順序就是先建立根 往左找到底換 往右找 把整棵樹建回來，只能說真的很簡潔== (preorder的Traverse方式)

不用檢查 i 的邊介值因為 JS array 存取超出是 undefined 剛好會等於 stop一開始的undefined

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34538/My-Accepted-Java-Solution

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34543/Simple-O(n)-without-map