剑指 Offer 07 重建二叉树

概述

https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

动态规划法

前序遍历的结果中，元素的排列顺序为：root，left subtree，right subtree；

中序遍历的结果中，元素的排列顺序为：left subtree，root，right subtree；

当我们构造二叉树时，首先确定根节点，之后递归确定左右子树。

为此，我们需要：

1. 确定根节点：即前序遍历结果中的第一项；
2. 确定左右子树的元素范围：根据上一点中确定得到的 root，找出其在中序遍历结果中的索引，减去其起始索引，即可得到左子树的元素个数，进而得到右子树的元素个数。

至于如何确定 root 元素的索引，我这里是先构造了一个 map。

时间复杂度 O(n)。

class Solution {
public:
    map<int, int> inorderMap;

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

    TreeNode *helper(vector<int> &preorder, vector<int> &inorder, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight) {
            return nullptr;
        }
        auto root = new TreeNode(preorder[preLeft]);
        int inIdx = inorderMap[preorder[preLeft]];
        int numLeft = inIdx - inLeft;
        root->left = helper(preorder, inorder, preLeft + 1, preLeft + numLeft, inLeft, inIdx - 1);
        root->right = helper(preorder, inorder, preLeft + numLeft + 1, preRight, inIdx + 1, inRight);
        return root;
    }
};

Links: sword-offer-07

未经允许，禁止转载，本文源站链接：https://iamazing.cn/