首页 > 剑指offer：面试题07. 重建二叉树

剑指offer：面试题07. 重建二叉树

题目： 重建二叉树

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

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3/ 9  20/  15   7

限制：

0 <= 节点个数 <= 5000

解题：

  • 前序遍历：先访问根结点，再访问左子结点，最后访问右子结点。
  • 中序遍历：先访问左子结点，再访问根结点，最后访问右子结点。
  • 后序遍历：先访问左子结点，再访问右子结点，最后访问根结点。
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:unordered_map mp;vector Pre, In;TreeNode* buildTree(vector& preorder, vector& inorder) {Pre = preorder, In = inorder;int n = Pre.size();for(int i = 0; i < n; i++) mp[In[i]] = i;return dfs(0, n-1, 0, n-1);}TreeNode* dfs(int pL, int pR, int inL, int inR){if(pL > pR) return nullptr;auto root = new  TreeNode(Pre[pL]);int k = mp[root->val];int left = k - inL;root->left = dfs(pL+1, pL + left, inL, k - 1);root->right = dfs(pL + left + 1, pR, k + 1, inR);return root;}
};

 

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • jquery判断方法是否存在_判断图中是否有环的三种方法

    0、什么是环？在图论中，环（英语：cycle）是一条只有第一个和最后一个顶点重复的非空路径。在有向图中，一个结点经过两种路线到达另一个结点，未必形成环。1、拓扑排序1.1、无向图使用拓扑排序可以判断一个无向图中是否存在环，具体步骤如下：求出图中所有结点的度。将所有度 <= 1 的结点入队。（独立结点的度为 0）当队列不空时，弹出队首元...

  • 简单的平衡二叉树

    已知一个长度为11的线性表List=(12, 24, 36, 90, 52, 30, 41, 8, 10, 38, 61)，试回答下面问题 （1）将线性表元素依次插入一个空的平衡二叉树，画出所得平衡二叉树，如果假设每个元素查找概率相同，则平均查找长度为多少？   (1) 插入12, 这是第一个结点,是根结点.   (2) 插入...

  • 有一个1亿结点的树,已知两个结点, 求它们的最低公共祖先!

    对该问题,分为如下几种情形讨论: 情形一: 假如该树为二叉树,并且是二叉搜索树, 依据二叉搜索树是排过序的, 我们只需要从树的根结点开始,逐级往下,和两个输入的结点进行比较. 如果当前结点的值比两个结点的值都大,那么最低的公共祖先一定在当前结点的左子树中,下一步遍历当前结点的左子节点. 如果当前结点的值比两个结点的值都小,那么...

  • （点）分治学习笔记

    哗我看了一下好像没有很详细专门讲分治的blog？那就主要先学一下点分治吧，其他的……等我记得把C++一本通带到机房来再说吧先咕着啦 写在前面 刷题进度 入门题（0/3） 好题(0/9) 问题解决进度 Q1 Q2  正文 淀粉质 点分治 点分治就是在一棵树上，对具有某些限定条件的途径静态地进行统计的算法。 ——《算法竞赛 进阶指南》...

  • B树，B+树，B-树和B*树

    B树        即二叉搜索树：        1.所有非叶子结点至多拥有两个儿子（Left和Right）；        2.所有结点存储一个关键字；        3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；        如：               ...

  • 只需三分钟您就可以用nodejs搭建静态网页服务器（配置静态网页访问目录）

    Node.js 中文网Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行环境。Node.js 使用了一个事件驱动、非阻塞式 I/O 的模型，使其轻量又高效。Node.js 的包管理器 npm，是全球最大的开源库生态系统。http://nodejs.cn/先安装nodejs 在自己的网站项目文件夹根目录...

  • 引用类型(一)：Object类型

    对象表示方式   1、第一种方式：使用new操作符后跟Object构造函数 var person = new Object();
    person.name = 'Nicholas';
    person.age = 29; 2、对象字面量表示法 var person = {name:'Nicholas',ag...

  • 【Step By Step】将Dotnet Core部署到Docker下

    一、使用.Net Core构建WebAPI并访问Docker中的Mysql数据库 这个的过程大概与我之前的文章《尝试.Net Core—使用.Net Core + Entity FrameWork Core构建WebAPI（一）》一致。 但是在我们这里，由于docker中无法部署sql server，所以我采用了Mysql数据库，顺便...

©2024 11GX.COM