LeetCode[Tree]: Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

這類問題非常适合用遞歸做，遞歸思路如下：

前序周遊的第一個節點必然是根節點，中序周遊中根節點之前的節點必然是根節點的左子樹，之後的節點必然是根節點的右子樹。以此為基礎，分别對根節點的左子樹和右子樹進行遞歸調用即可生成整棵二叉樹。

基于這個思路，我的C++代碼實作如下：

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    if (preorder.empty()) return nullptr;

    TreeNode *root = new TreeNode(preorder[0]);
    int leftNodes  = find(inorder.begin(), inorder.end(), preorder[0]) - inorder.begin();
    int rightNodes = inorder.size() - 1 - leftNodes;

    if (leftNodes) {
        vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + leftNodes + 1);
        vector<int> leftInorder ( inorder.begin()     ,  inorder.begin() + leftNodes);
        root->left = buildTree(leftPreorder, leftInorder);
    }

    if (rightNodes) {
        vector<int> rightPreorder(preorder.end() - rightNodes, preorder.end());
        vector<int> rightInorder ( inorder.end() - rightNodes,  inorder.end());
        root->right = buildTree(rightPreorder, rightInorder);
    }

    return root;
}
           

但是我得到了“Memory Limit Exceeded”的結果，這是由于生成左子樹的前序周遊、中序周遊、右子樹的前序周遊、中序周遊所生成的數組所耗費的記憶體空間，可以通過疊代器來訓示左子樹、右子樹的範圍來避免這個問題：

class Solution1 {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return buildTreeHelper(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }

    TreeNode *buildTreeHelper(vector<int> ::iterator preBegin, vector<int> ::iterator preEnd, vector<int> ::iterator inBegin, vector<int> ::iterator inEnd) {
        if (preEnd <= preBegin) return nullptr;

        TreeNode *root = new TreeNode(*preBegin);
        int leftNodes  = find(inBegin, inEnd, *preBegin) - inBegin;
        root->left  = buildTreeHelper(preBegin + 1, preBegin + leftNodes + 1, inBegin, inBegin + leftNodes);
        root->right = buildTreeHelper(preBegin + leftNodes + 1, preEnd, inBegin + leftNodes + 1, inEnd);

        return root;
    }
};
           

疊代算法可以參考這個Discuss。