根据二叉树的前序遍历和中序遍历重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10
11    struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
12         if(pre.size()==0||in.size()==0)
13         {
14             return NULL;
15         }
16         if(pre.size()==1)
17         {
18             return new TreeNode(pre.front());
19         }
20         if(in.size()==1)
21         {
22             return new TreeNode(in.front());
23         }
24         int node_Val=pre.front();//用来存根节点的值
25         auto node_in=find(in.begin(),in.end(),node_Val);//根节点在in的位置
26
27         //左子树区间
28         vector<int> left_in_Block(in.begin(),node_in);
29         int move=node_in-in.begin();
30         vector<int> left_pre_Block(++pre.begin(),pre.begin()+move+1);
31
32         //右子树区间
33         vector<int> right_in_Block(++node_in,in.end());
34         vector<int> right_pre_Block(pre.begin()+move+1,pre.end());
35
36         TreeNode *node=new TreeNode(node_Val);//根节点
37         node->left=reConstructBinaryTree(left_pre_Block,left_in_Block);
38         node->right=reConstructBinaryTree(right_pre_Block,right_in_Block);
39         return node;
40     }
时间: 09-18

根据二叉树的前序遍历和中序遍历重建二叉树的相关文章

已知二叉树的前序遍历、中序遍历或者中序遍历、后序遍历求二叉树结构的算法

二叉树中的前序遍历是先访问根结点,再访问左子树,右子树. 中序遍历是先访问左子树,再是根结点,最后是右子树. 后序遍历是先访问左子树,再是右子树,最后是根结点. 算法思路是先根据前序遍历的第一个结点或者后序遍历的最后一个结点,查找对应在中序遍历中的位置,就可以确定左子树包含的元素和右子树包含的元素,最后通过递归来实现就可以了. 二叉树的表示形式为 //二叉树的结构表示为 class TreeNode { int val; TreeNode left; TreeNode right; TreeNo

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

问题描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字.例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回. 思路: 在二叉树的前序遍历序列中,第一个数字总是树的根结点的值.但在中序遍历序列中,根结点的值在序列的中间,左子树的结点的值位于根结点的值的左边,而右子树的结点的值位于根结点的值的右边.因此我们需要扫描中序遍历序列,才能找到根结点的值. 如下图所示,

前序遍历和中序遍历重建二叉树

对于二叉树,在此我不做过多讲解,如有不懂,请参照一下链接点击打开链接 1.在此二叉树的定义: struct BinaryTreeNode     {         BinaryTreeNode<T> *_Left;         BinaryTreeNode<T> *_Right;         T _data;     public:         BinaryTreeNode(const T& x)             :_Left(NULL)       

二叉树(14)----由前序遍历和中序遍历重建二叉树

1.二叉树定义 typedef struct BTreeNodeElement_t_ { void *data; } BTreeNodeElement_t; typedef struct BTreeNode_t_ { BTreeNodeElement_t *m_pElemt; struct BTreeNode_t_ *m_pLeft; struct BTreeNode_t_ *m_pRight; } BTreeNode_t; 二.根据前序遍历序列和中序遍历序列重建二叉树 算法说明: 由中序遍历序

已知二叉树的前序遍历和中序遍历,如何得到它的后序遍历?

对一棵二叉树进行遍历,我们可以采取3中顺序进行遍历,分别是前序遍历.中序遍历和后序遍历.这三种方式是以访问父节点的顺序来进行命名的.假设父节点是N,左节点是L,右节点是R,那么对应的访问遍历顺序如下: 前序遍历    N->L->R 中序遍历    L->N->R 后序遍历    L->R->N /***************************************************************************************

027依据前序遍历和中序遍历,重建二叉树(keep it up)

剑指offer中题目:http://ac.jobdu.com/problem.php?pid=1385 题目描写叙述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.如果输入的前序遍历和中序遍历的结果中都不含反复的数字. 比如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并输出它的后序遍历序列. 输入: 输入可能包括多个測试例子,对于每一个測试案例, 输入的第一行为一个整数n(1<=n<=1000):代表二叉树的节点

二叉树的遍历规则(前序遍历、后序遍历、中序遍历)

今天看了一些关于平和查找二叉树的问题,顺便也复习了一下二叉树的遍历规则,写一下学习文档. 树的遍历顺序大体分为三种:前序遍历(先根遍历.先序遍历),中序遍历(中根遍历),后序遍历(后根遍历). 如图所示二叉树: 前序遍历:前序遍历可以记为根左右,若二叉树为空,则结束返回. 前序遍历的规则: (1)访问根节点 (2)前序遍历左子树 (3)前序遍历右子树 这里需要注意:在完成第2,3步的时候,也是要按照前序遍历二叉树的规则完成. 前序遍历的输出结果:ABDECF 中序遍历:中序遍历可以记为左根右,也

知道前序遍历和中序遍历编写程序得到二叉树

// BinaryTree.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include <iostream> using namespace std; struct BTreeNode { int m_nValue; BTreeNode* m_pLeft; BTreeNode* m_pRight; }; BTreeNode* ConstructCore(int* startPreorder, int* endPreorder,

题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树

问题描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字.例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回. 思路: 在二叉树的前序遍历序列中,第一个数字总是树的根结点的值.但在中序遍历序列中,根结点的值在序列的中间,左子树的结点的值位于根结点的值的左边,而右子树的结点的值位于根结点的值的右边.因此我们需要扫描中序遍历序列,才能找到根结点的值. 如下图所示,