題目敘述

題目難度: Medium
題目敘述: 給定兩個整數 inorder 和 postorder 分別代表對一個 binary tree 進行 inorder traversal 和 postorder traversal 的結果，請建構一棵二元樹，並回傳二元樹的 root。

解法

一開始的想法

這題算是 LeetCode 105 的延伸題目。

其實有想法很像:

Inorder 的第一個元素是 leftmost 元素
Preorder 的最後一個元素會是 root

因此每次迭代過程中，透過 postorder 中找到的 root 節點值，來去找到 inorder 中的 subTree 該怎麼切分左右子樹

我的解法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTreeHelper(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd){
        if(inStart> inEnd || postStart > postEnd) return nullptr;
        int rootVal = postorder[postEnd];
        TreeNode* root = new TreeNode(rootVal);

        // divided into subArrays
        int mid;
        for(mid= inStart; mid <=inEnd; mid++){
            if(inorder[mid]==rootVal){
                break;
            }
        }
        
        int leftTreeSize = mid - inStart;
        root -> left = buildTreeHelper(inorder, postorder,inStart, mid-1, postStart, postStart+leftTreeSize-1 );
        root -> right = buildTreeHelper(inorder, postorder, mid+1, inEnd,postStart+leftTreeSize, postEnd-1);
        return root;
    }


    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder){
        if(inorder.size()==0 || postorder.size()==0) return nullptr;
        return buildTreeHelper(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
    }
};

整體作法跟 LeetCode-105 很像都是額外建立一個 helper 函數，每次迭代過程中找到用來在陣列區分左右子樹的中間值的index，找到在 inorder 當中的分界值就可以 break 了。

之後就是透過下面這樣的 pattern 來建構樹

1 2	root->left = buildTree(左子樹inorder陣列，左子樹postorder陣列) root->right = buildTree(右子樹inorder陣列，右子樹postorder陣列)

執行結果

更好的做法

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        unordered_map<int, int> index;
        for (int i = 0; i < inorder.size(); i++) {
            index[inorder[i]] = i;
        }
        return buildTreeHelper(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1, index);
    }
    
    TreeNode* buildTreeHelper(vector<int>& inorder, vector<int>& postorder, int inorderStart, int inorderEnd, int postorderStart, int postorderEnd, unordered_map<int, int>& index) {
        if (inorderStart > inorderEnd || postorderStart > postorderEnd) {
            return nullptr;
        }
        int rootVal = postorder[postorderEnd];
        TreeNode* root = new TreeNode(rootVal);
        int inorderRootIndex = index[rootVal];
        int leftSubtreeSize = inorderRootIndex - inorderStart;
        root->left = buildTreeHelper(inorder, postorder, inorderStart, inorderRootIndex - 1, postorderStart, postorderStart + leftSubtreeSize - 1, index);
        root->right = buildTreeHelper(inorder, postorder, inorderRootIndex + 1, inorderEnd, postorderStart + leftSubtreeSize, postorderEnd - 1, index);
        return root;
    }
};