重建二叉树

2023-10-01 21:41:28

1.题目

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

注意:

二叉树中每个节点的值都互不相同；
输入的前序遍历和中序遍历一定合法；

样例

给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
    3
   / \
  9  20
    /  \
   15   7

这是题目地址，有兴趣的可以做一下。

2.时间复杂度为O(nlogn)的解法

这个是自己做的，准确来说算是实践了一下自己上数据结构课学到的知识吧。

2.1 思路

如果前序序列不为空，那么第一个数一定是树的根。我们再从中序序列找到这个数所在的位置，左半部分就是根的左子树，右半部分就是根的右子树，我们可以把左子树再当作一棵树，适当缩小先序序列的范围，第一个数就是这个左子树的根，然后再在中序序列去寻找这个数，继续划分，依此类推，当序列只剩下一个数时，代表我们找到了叶子节点，就不需要再继续划分了。

道理很简单，但是操作起来出了点问题，还是边界问题，要亲自实现一遍才知道自己哪里有问题。

自己的代码也蛮复杂的，没有用一些数记录下标，直接将序列缩小进行递归，如果是利用下标值，可以不需要这么复杂。（此处就不修改代码了）

2.2 代码

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void insertToTree(TreeNode* T, vector<int> preorder, vector<int> inorder) {
    T->val = preorder[0];
    //当此时数组中只有一个数时，表示当前节点无左右孩子，为树叶
    if (inorder.size() == 1)
        return;
    int i = 0;
    //寻找该数在中序数组中的位置，左半部分为其左子树，右半部分为其右子树。
    for (; i < inorder.size(); i++) {
        if (inorder[i] == T->val)
            break;
    }
    //此时位于中序数组第一位，表明无左孩子
    if (i == 0) {
        T->left = NULL;
        T->right = new TreeNode(0);
        insertToTree(T->right, vector<int>(preorder.begin() + i + 1, preorder.end()), vector<int>(inorder.begin() + i + 1, inorder.end()));
    }
    //位于中序数组最后一位，表明无右孩子
    else if (i == inorder.size() - 1) {
        T->right = NULL;
        T->left = new TreeNode(0);
        insertToTree(T->left, vector<int>(preorder.begin() + 1, preorder.begin() + i + 1), vector<int>(inorder.begin(), inorder.begin() + i));
    }
    //有左右孩子
    else {
        T->right = new TreeNode(0);
        T->left = new TreeNode(0);
        insertToTree(T->left, vector<int>(preorder.begin() + 1, preorder.begin() + i + 1), vector<int>(inorder.begin(), inorder.begin() + i));
        insertToTree(T->right, vector<int>(preorder.begin() + i + 1, preorder.end()), vector<int>(inorder.begin() + i + 1, inorder.end()));
    }
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    //如果是空序列，返回空树
    if (inorder.size() == 0) return NULL;
    TreeNode* T = new TreeNode(0);
    insertToTree(T, preorder, inorder);
    return T;
}

3.时间复杂度为O(n)的解法

这是题解，还是学的知识没用上，忘记了散列表这么好用的东西。

大佬的题解的原地址

3.1 思路

思路和我自己想的是基本一样的，只不过大佬在中序序列找数的这个过程中用的是散列表（学了一直没用过，导致现在都不会用）

3.2 代码

unordered_map<int,int> pos;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; i ++ )
            pos[inorder[i]] = i;
        return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* dfs(vector<int>&pre, vector<int>&in, int pl, int pr, int il, int ir)
    {
        if (pl > pr) return NULL;
        int k = pos[pre[pl]] - il;
        TreeNode* root = new TreeNode(pre[pl]);
        root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1);
        root->right = dfs(pre, in, pl + k + 1, pr, il + k + 1, ir);
        return root;
    }

作者：yxc
链接：https://www.acwing.com/solution/content/706/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

码农公寓