美文网首页
面试题7:重建二叉树

面试题7:重建二叉树

作者: hxy159 | 来源:发表于2019-10-10 12:34 被阅读0次

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

算法:递归

思路:1)利用前序遍历找根节点,即前序遍历的第一个值就是根节点的值
2)利用中序遍历找左右子树,通过前序遍历的第一个值找到中序遍历该值的下标,其左边为左子树,右边为右子树
3)通过中序遍历划分出来的左右子树个数找前序遍历的左右子树,假设中序遍历的找到的左子树个数为l,则前序
遍历根节点后面l个数时左子树,其余后面的数为右子树
4)递归构造左右子树

时间复杂度:O(n)

unordered_map<int, int> hash;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = preorder.size();
    // 将中序遍历每个数对应的下标存入哈希表,方便从根节点的值找到中序下标
    for(int i = 0;i < n;i ++) hash[inorder[i]] = i;
    return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
    
}

TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir)
{
    if(pl > pr) return NULL;
    int val = preorder[pl];
    int k = hash[val];
    int len = k - il;
    auto root = new TreeNode(val);
    root -> left = dfs(preorder, inorder, pl + 1, pl + len, il, k - 1);
    root -> right = dfs(preorder, inorder, pl + len + 1, pr, k + 1, ir);
    return root;
}

相关文章

  • 重建二叉树

    《剑指offer》面试题7:重建二叉树 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前...

  • 剑指Offer-二叉树

    面试题7:重建二叉树 题目: 输入某二叉树的前序遍历和中序遍历的结果。请重建该二叉树。假设输入的前序遍历和中序遍历...

  • 2.3.4 树

    面试题7:重建二叉树 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果...

  • LeetCode | 面试题07. 重建二叉树【剑指Offer】

    LeetCode 面试题07. 重建二叉树【剑指Offer】【Medium】【Python】【二叉树】【递归】 问...

  • 剑指offer第二版-7.重建二叉树

    本系列导航:剑指offer(第二版)java实现导航帖 面试题7:重建二叉树 题目要求:根据二叉树的前序遍历和中序...

  • 面试题7:重建二叉树

    【题目描述】输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重...

  • 面试题7:重建二叉树

    题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重...

  • 面试题7:重建二叉树

  • 面试题7:重建二叉树

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 ...

  • 面试题7: 重建二叉树

网友评论

      本文标题:面试题7:重建二叉树

      本文链接:https://www.haomeiwen.com/subject/lqiopctx.html