WEI-CHENG CHEN

說明

給前序跟中序，建立初二元樹

解法

前序遍歷順序（preorder）：[ 根 左子樹 右子樹 ]
中序遍歷順序（inorder）：[ 左子樹 根 右子樹 ]
  1. 前序第一個值 就是「根節點」
  2. 在「中序遍歷」裡找這個根的位置，根左邊的就是左子樹、右邊的是右子樹
  3. 根據這個劃分，找出對應的左右子樹區段

假設 preorder = [3, 9, 20, 15, 7]

inorder = [9, 3, 15, 20, 7]

還有一件事，在【inorder 找左右子樹位置】時，如果用線性找太慢了

class Solution {
public:
    TreeNode* f(map<int, int>& m, vector<int>& preorder, vector<int>& inorder,
                int preorder_left,  // 前序遍歷起點索引
                int preorder_right,  // 前序遍歷終點索引
                int inorder_left, // 中序遍歷起點索引
                int inorder_right // 中序遍歷終點索引
    ){
        // 結束條件：以preorder去看(preorder可以知道 現在跟節點建立到哪裡)
        if(preorder_left > preorder_right) return nullptr;


        int root_val = preorder[preorder_left]; // 前序的第一個節點就是 root
        int root_index = m[preorder[preorder_left]]; // 查 root 在 inorder 的位置


        TreeNode* root = new TreeNode(root_val);

        // 到這邊，已經知道3是根節點了
        // 計算左子樹大小
        // preorder = [3, 9, 20, 15, 7]
        // inorder = [9, 3, 15, 20, 7]
        // 接下來，如何在preorder與inorder中去切出左右子樹
        // 只有一種方式：在inorder可以看出左右子樹
        // 左子樹的各數 = root_index - preorder_left
        int left_subtree = root_index - inorder_left;


        root->left = f(m, preorder, inorder,
            preorder_left+1, preorder_left + left_subtree, // preorder中左子樹間隔
            inorder_left, root_index-1 // inorder中左子樹間隔
            );
        root->right = f(m, preorder, inorder,
            preorder_left + left_subtree + 1, preorder_right, // preorder中右子樹間隔
            root_index + 1, inorder_right // inorder中右子樹間隔
            );
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // key = inorder 中的值, value = inorder 中的值的位置
        map<int, int> m;
        int n = inorder.size();
        for(int i=0;i<n;i++){
            m[inorder[i]] = i;
        }
        return f(m, preorder, inorder, 0, n-1, 0, n-1);
    }
};