跳转至

105 从前序与中序遍历构造二叉树

直接做法

/**
 * 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 {
private:
    TreeNode* myBuildTree(vector<int>& preorder, vector<int>& inorder, int preorderStart, int preorderEnd, int inorderStart, int inorderEnd){
        if(preorderStart > preorderEnd || inorderStart > inorderEnd)
            return nullptr;
        auto it = find(inorder.begin()+inorderStart, inorder.begin()+inorderEnd + 1, preorder[preorderStart]);
        int pos = distance(inorder.begin(), it);
        int leftSubTreeNum = pos - inorderStart;
        TreeNode* root = new TreeNode(inorder[pos]);
        root->left = myBuildTree(preorder,inorder,preorderStart + 1, preorderStart + leftSubTreeNum, inorderStart, pos - 1);
        root->right = myBuildTree(preorder,inorder, preorderStart + leftSubTreeNum + 1, preorderEnd, pos + 1, inorderEnd);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return myBuildTree(preorder, inorder,0,preorder.size() - 1, 0, inorder.size() - 1);
    }
};

直接做法的优化

find的时间复杂度为\(O(n)\),可以进一步优化为哈希表查询,时间复杂度改为\(O(1)\)

/**
 * 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 {
private:
    TreeNode* myBuildTree(vector<int>& preorder, vector<int>& inorder, int preorderStart, int preorderEnd, int inorderStart, int inorderEnd){
        if(preorderStart > preorderEnd || inorderStart > inorderEnd)
            return nullptr;
        int pos = hashMap[preorder[preorderStart]];
        int leftSubTreeNum = pos - inorderStart;
        TreeNode* root = new TreeNode(inorder[pos]);
        root->left = myBuildTree(preorder,inorder,preorderStart + 1, preorderStart + leftSubTreeNum, inorderStart, pos - 1);
        root->right = myBuildTree(preorder,inorder, preorderStart + leftSubTreeNum + 1, preorderEnd, pos + 1, inorderEnd);
        return root;
    }
public:
    unordered_map<int, int> hashMap;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); i++){
            hashMap[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder,0,preorder.size() - 1, 0, inorder.size() - 1);
    }
};

时间复杂度:O(n),其中 n 是树中的节点个数。

空间复杂度:O(n),除去返回的答案需要的 O(n) 空间之外,我们还需要使用 O(n) 的空间存储哈希映射,以及 O(h)(其中 h 是树的高度)的空间表示递归时栈空间。这里 h<n,所以总空间复杂度为 O(n)。

迭代

待补充