leetcode105：从前序与中序遍历序列构造二叉树

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

// 二叉树结点的定义
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) {}
};

const int NULL_NODE = -101;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    使用前序遍历的第一个节点作为根节点。
    在中序遍历中找到根节点的位置，从而确定左子树和右子树的范围。
    递归地构造左子树和右子树。

    时间复杂度：O(n)
        其中 n 是树中的结点个数。
        每次递归中，在中序遍历中查找根节点的位置，时间复杂度为 O(n)。
        由于递归调用的深度为树的高度，总的时间复杂度为 O(n^2)。
        使用哈希表存储中序遍历中每个值的索引，查找根节点的时间复杂度可以优化到 O(1)。
    空间复杂度：O(n)
        递归调用的深度为树的高度。
        最坏情况下（树完全不平衡）为 O(n)，最好情况下（树完全平衡）为 O(logn)。
        使用哈希表存储中序遍历的索引，空间复杂度为 O(n)。
*/
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        // 构建中序遍历的值到索引的映射
        for (int i = 0; i < inorder.size(); i++) {
            indexMap[inorder[i]] = i;
        }

        // 调用递归函数构建二叉树
        return build(0, preorder.size()-1, 0, inorder.size()-1);
    }

    TreeNode* build(int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight) {
            return nullptr;
        }

        // 前序遍历的第一个元素是根节点
        int rootVal = preorder[preLeft];
        TreeNode* root = new TreeNode(rootVal);
        // 在中序遍历中找到根节点的位置
        int inRoot = indexMap[rootVal];
        // 计算左子树的大小
        int leftSubtreeSize = inRoot - inLeft;

        // 递归构建左右子树
        root->left = build(preLeft+1, preLeft+leftSubtreeSize, inLeft, inRoot-1);
        root->right = build(preLeft+leftSubtreeSize+1, preRight, inRoot+1, inRight);

        return root;
    }

private:
    unordered_map<int, int> indexMap; // 中序遍历的值到索引的映射
    vector<int> preorder; // 前序遍历数组
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<vector<int>> preorder_cases = {
        {3,9,20,15,7},
        {1}
    };
    vector<vector<int>> inorder_cases = {
        {9,3,15,20,7},
        {1}
    };

    for (size_t i = 0; i < preorder_cases.size(); i++) {
        auto& preorder = preorder_cases[i];
        auto& inorder = inorder_cases[i];

        cout << "preorder = ";
        printArray(preorder);
        cout << "inorder = ";
        printArray(preorder);

        // 构建二叉树
        TreeNode* root = solution.buildTree(preorder, inorder);
        cout << "Output: ";
        levelOrderTraversal(root);

        // 释放内存
        deleteTree(root);
    }

    return 0;
}