剑指 Offer 07 重建二叉树

剑指-Offer 2021-11-23 12:07:00 2021-11-24 21:32:23 64 次浏览

概述

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

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

动态规划法

前序遍历的结果中,元素的排列顺序为:rootleft subtreeright subtree

中序遍历的结果中,元素的排列顺序为:left subtreerootright 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;
    }
};

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