105 Construct Binary Tree from Preorder and Inorder Traversal && 106 Construct Binary Tree from Inorder and Postorder Traversal

題目意思很簡單，給你前序跟中序, 要你組出一棵數

其實這個題目我印象很深刻, 這基本上是台灣考資工研究所的必考題, 這應該每個人都會寫, 但問題來了, 要怎麼用程式做呢

前序中序的基本概念這邊就不贅述了, 我們了解到

前序的第一個點一定是root

root能將中序分成左右子樹

於是我們我需要找到root在中序到底是位在哪個index, 即可將左右子樹給分出來

好問題來了, 如果找到root在中序的index, 要怎麼細分左子樹的頭尾, 跟右子樹的頭尾

我們先從左子樹開始

左:

preorder:

頭:preorder的頭index, 就是原本preorder_left + 1, 1是哪來的, preorder_left及為 root, 跳過這個root就是左子樹的頭

左preorder頭:preorder_left + 1

尾: 我們可以透過inorder找到的index, 判斷左子數的node數, 總共為 i — inorder_left個, 最後再從頭跑到尾 就是 preorder_left + i -inorder_left

左preorder尾: preorder_left+ i -inorder_left

inorder:

頭: 就是最左邊的值, inorder_left

左inorder頭: inorder_left

尾: root左邊那個就是了

左inorder尾: i -1

搞定了左子樹, 接下來換右子樹

右：

preorder:

頭: 就是剛剛左子樹preorder尾 + 1

右preorder頭: preorder_left+ i -inorder_left + 1

尾: preorder的最後一個

右preorder尾: preorder_right

inorder:

頭: root的右邊一位

右inorder頭: index+1

尾: inorder的最後一個

右inorder尾: inorder_right

code:

class Solution {
  public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder, int p_left,
                        int p_right, int i_left, int i_right) {
        if (p_left > p_right || i_left > i_right) {
            return nullptr;
        }
        int root_index = i_left; // in inorder, root index
        int root_val = preorder[p_left];
        for (; root_index <= i_right; root_index++) {
            if (root_val == inorder[root_index]) {
                break;
            }
        }
        TreeNode *cur = new TreeNode(root_val);
        int left_number = root_index - i_left;
        cur->left = buildTree(preorder, inorder, p_left + 1,
                              p_left + left_number, i_left, root_index - 1);
        cur->right = buildTree(preorder, inorder, p_left + left_number + 1,
                               p_right, root_index + 1, i_right);
        return cur;
    }
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return buildTree(preorder, inorder, 0, preorder.size() - 1, 0,
                         inorder.size() - 1);
    }
};

中序後序的概念幾乎一樣, 就是找法要變動一下而已, 這邊就不多加說明了

class Solution {
  public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder,
                        int i_left, int i_right, int post_left,
                        int post_right) {
        if (i_left > i_right || post_left > post_right) {
            return nullptr;
        }
        int root_value = postorder[post_right];
        int root_index = i_left; // root index in inorder vector
        for (; root_index <= i_right; root_index++) {
            if (root_value == inorder[root_index]) {
                break;
            }
        }
        TreeNode *root = new TreeNode(root_value);
        int left_tree_number = root_index - i_left;
        root->left = buildTree(inorder, postorder, i_left, root_index - 1,
                               post_left, post_left + left_tree_number - 1);
        root->right = buildTree(inorder, postorder, root_index + 1, i_right,
                                post_left + left_tree_number, post_right - 1);
        return root;
    }
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        return buildTree(inorder, postorder, 0, inorder.size() - 1, 0,
                         postorder.size() - 1);
    }
};