重建二叉树-白红宇

重建二叉树

阅读量：6692 次

发布时间：2019-06-25

本文共 1952 字，大约阅读时间需要 6 分钟。

题目描述

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

基本思想：在中序序列中找到根节点的位置，根结点左边是左子树，右边是右子树。然后分别对左子树和右子树进行递归处理。

在打印树的函数上，我的实现方法是广度优先遍历，也就是按层打印二叉树。

#include 
      
       #include 
       
        #include "string.h"#include "stdio.h"#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include
            #include
             
              #include "math.h"using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Tree{public: void PrintTree(TreeNode* pRoot) { if(pRoot == NULL) return; int level = 0; int index = 0; int globle = 0; queue
              
                queue; queue.push(pRoot); while(!queue.empty()) { TreeNode* pNode = queue.front(); cout<
               
                val<<" "; queue.pop(); if(pNode->left) { queue.push(pNode->left); } if(pNode->right) { queue.push(pNode->right); } } }};class Solution {public: TreeNode* reConstructBinaryTree(vector
                
                  pre,vector
                 
                   vin) { if(pre.size() == NULL || pre.size() == NULL || pre.size()!=vin.size()) return NULL; vector
                  
                    pre_left; vector
                   
                     pre_right; vector
                    
                      vin_left; vector
                     
                       vin_right; int index = 0; for(int i=0;i
                      
                       index) { vin_right.push_back(vin[i]); pre_right.push_back(pre[i]); } } TreeNode* pRoot = new TreeNode(pre[0]); pRoot->left = reConstructBinaryTree(pre_left,vin_left);//递归左子树 pRoot->right = reConstructBinaryTree(pre_right,vin_right);//递归右子树 return pRoot; }};int main(){ vector
                       
                         pre; pre.push_back(1); pre.push_back(2); pre.push_back(4); pre.push_back(7); pre.push_back(3); pre.push_back(5); pre.push_back(6); pre.push_back(8); vector
                        
                          vin; vin.push_back(4); vin.push_back(7); vin.push_back(2); vin.push_back(1); vin.push_back(5); vin.push_back(3); vin.push_back(8); vin.push_back(6); Solution solution; Tree tree; TreeNode* p = solution.reConstructBinaryTree(pre,vin); tree.PrintTree(p);}

转载于:https://www.cnblogs.com/omelet/p/6648345.html

你可能感兴趣的文章