[LC]105.从前序与中序遍历序列构造二叉树

题目

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

分析

先序序列的第一个元素是树的根，在中序序列中定位到这个元素，该元素的左边都是左子树中的结点，右边都是右子树中的结点，据此，可以将问题规约为两个更小的子问题，递归求解。

代码

/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0,
                               inorder.size() - 1);
    }
    TreeNode* buildTreeHelper(vector<int>& preorder, size_t l1, size_t r1,
                              vector<int>& inorder, size_t l2, size_t r2) {
        if (l1 > r1 || l2 > r2) return nullptr;
        if (l1 == r1)
            return new TreeNode(preorder[l1]);
        auto root_iter = find(inorder.cbegin(), inorder.cend(), preorder[l1]);
        size_t root_pos = root_iter - inorder.begin();
        size_t left_size = root_pos - l2, right_size = r2 - root_pos;
        TreeNode* root = new TreeNode(preorder[l1]);
        root->left = buildTreeHelper(preorder, l1 + 1, l1 + left_size, inorder,
                                     l2, root_pos - 1);
        root->right = buildTreeHelper(preorder, l1 + left_size + 1, r1, inorder,
                                      root_pos + 1, r2);
        return root;
    }
};

时间复杂度

可以得到平均时间复杂度的递推方程$A(n) = \frac{2}{n} \Sigma_{i=1}^{n-1}A(i) + O(n).$

解得$A(n) = \Theta(nlogn).$

优化：

如果我们在处理之前，先将indorder数组的值和其下表建立一个哈希映射，那么我们每次递归的时候平均只需要$O(1)$的时间就可以在inorder中找到树的根。

代码：

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (size_t i = 0; i != inorder.size(); ++i)
            val_to_posi_[inorder[i]] = i;
        return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0,
                               inorder.size() - 1);
    }
    TreeNode* buildTreeHelper(vector<int>& preorder, size_t l1, size_t r1,
                              vector<int>& inorder, size_t l2, size_t r2) {
        if (l1 > r1 || l2 > r2) return nullptr;
        if (l1 == r1)
            return new TreeNode(preorder[l1]);
        size_t root_pos = val_to_posi_[preorder[l1]];
        size_t left_size = root_pos - l2, right_size = r2 - root_pos;
        TreeNode* root = new TreeNode(preorder[l1]);
        root->left = buildTreeHelper(preorder, l1 + 1, l1 + left_size, inorder,
                                     l2, root_pos - 1);
        root->right = buildTreeHelper(preorder, l1 + left_size + 1, r1, inorder,
                                      root_pos + 1, r2);
        return root;
    }
private:
    unordered_map<int, size_t> val_to_posi_;
};

时间复杂度：

优化后的递推方程为$A(n) = \frac{2}{n} \Sigma_{i=1}^{n-1}A(i) + O(1).$

解得$A(n) = \Theta(n).$