［刷題］106 Construct Binary Tree from Inorder and Postorder Traversal｜C++｜LeetCode

 

簡介：中等，題意為給予中序 (inorder)與後序(postorder)走訪二元樹 (binary tree)的順序 (traversal)，建構出原本的二元樹。


一、概念

中序 (inorder)與後序 (postorder)走訪二元樹的示意圖
橘色背景為子樹的根 (root of subtree)，藍箭頭為左子樹，粉箭頭為右子樹

（一）前中後走訪特性

以上圖右上角二元樹為例，其前中後序為：

  1. 前序：3,  9,  20,  15,  7
  2. 中序：9,  3,  15,  20,  7
  3. 後序：9,  15,  7,  20,  3

可以發現根與子樹位置是有規則的。

  1. 前序根為最左元素，中序根分開左右子樹，後序根為最右元素
  2. 前中後序左子樹位在右子樹左方，右子樹也在左子樹右方

綜合以上兩規則，只要給予前序與中序，即可透過根的位置知道左子樹大小，進而推敲出右子樹大小；同理如果給予後序與中序，也可透過根知道左右子樹大小。

（二）分治法 (divide and conquer)

題目是給中序與後序要我們建構二元樹，在綜合上述特性，我們可以使用分治法：

  1. 找根元素 (conquer)：後序最右元素必是根
  2. 找子樹大小 (divide)：得知根元素後，定位出中序的根元素，即可得知左右子樹大小


二、實作

（一）使用Map存中序的value-index

static TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    // 1. Store the index of inorder.
    unordered_map index;
    for (int i = 0; i < inorder.size(); ++i) {index[inorder[i]] = i;}
    // 2. Build a tree by inorder and postorder.
    return buildTreeHelper(inorder, postorder,
                           0, inorder.size() - 1,
                           0, postorder.size() - 1, index);
        
}

  1. 第一步為了快速在中序中定位出根元素的位置，我們使用unorder_map (hash table)去紀錄value與index的關係，定位時間複雜度為O(1)。
  2. 第二步直接使用遞迴函數，去建構二元樹。

（二）分治法建構二元樹

static TreeNode* buildTreeHelper(vector<int>& inorder,
                          vector<int>& postorder,
                          const int inorderStart,
                          const int inorderEnd,
                          const int postorderStart,
                          const int postorderEnd,
                          unordered_map<int>& index) {
    // 1. If Start > End, return NULL
    if (inorderStart > inorderEnd || postorderStart > postorderEnd) {return NULL;}
    // 2. Find root and the size of left subtree
    const int rootValue = postorder[postorderEnd];
    TreeNode* root = new TreeNode(rootValue);
    const int inorderRootIndex = index[rootValue];
    const int leftSubtreeSize = inorderRootIndex - inorderStart;
    // 3. Build the left subtree
    root->left = buildTreeHelper(inorder, postorder,
                                 inorderStart, inorderRootIndex - 1,
                                 postorderStart, postorderStart + leftSubtreeSize - 1, index);
    // 4. Build the right subtree
    root->right = buildTreeHelper(inorder, postorder,
                                  inorderRootIndex + 1, inorderEnd,
                                  postorderStart + leftSubtreeSize, postorderEnd - 1, index);
    return root;
}

主要有四部分：

  1. 檢查邊界：如果中序或後序頭與尾交錯，則代表此樹只剩下一個元素，無法在分割，故回傳NULL
  2. 找根元素與左右子樹大小
  3. 建構左子樹，左子樹邊界請參照上圖藍箭頭
  4. 建構右子樹，右子樹邊界請參照上圖粉箭頭


三、相關文章

請詳見LeetCode相關文章


四、參考文獻

留言

張貼留言