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。