数据结构 - 二叉树（重构 + 遍历）

本文主要是介绍数据结构 - 二叉树（重构 + 遍历），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

写在前面

昨天有同学问到我一题关于重构二叉树的问题(link)，做了一下，也做个记录吧！

所谓二叉树的重构，就是给你前序和中序，或者中序和后序，让你还原这棵二叉树.

注意：给出前序和后序是不能唯一确定一棵二叉树的，证明请看这儿.

一.给出前序和中序，重构二叉树

一个递归的过程：

当前结点的value：每一轮根据前序的第一个元素确定当前结点值.

左子树的中序遍历数组：以当前结点的value为分界点，将中序分为左部分和右部分，左部分即为左子树的中序遍历数组.

右子树的中序遍历数组：以当前结点的value为分界点，将中序分为左部分和右部分，右部分即为右子树的中序遍历数组.

左子树的前序遍历数组：pre[1 ... i] (i为左子树的中序遍历数组的个数).

右子树的前序遍历数组：pre[i+1 ... end]（i为左子树的中序遍历数组的个数）.

构造出这5个值，继续递归求左右子树即可.

题目1：重建二叉树（剑指offer）

给出前序和中序，要你重建二叉树.

按照上面所说递归即可,详见代码：

 /** 
  * ----------------------------------------------------------------- 
  * Copyright (c) 2016 crazyacking.All rights reserved. 
  * ----------------------------------------------------------------- 
  *       Author: crazyacking 
  *       Date  : 2016-01-03-21.09 
  */ 
 #include <queue> 
 #include <cstdio> 
 #include <set> 
 #include <string> 
 #include <stack> 
 #include <cmath> 
 #include <climits> 
 #include <map> 
 #include <cstdlib> 
 #include <iostream> 
 #include <vector> 
 #include <algorithm> 
 #include <cstring> 
 using namespace std; 
 typedef long long( LL); 
 typedef unsigned long long( ULL); 
 const double eps( 1e-8); 
 
 /** 
  * Definition for binary tree 
  * struct TreeNode { 
  *     int val; 
  *     TreeNode *left; 
  *     TreeNode *right; 
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
  * }; 
  */ 
 
 struct TreeNode 
 { 
     int val; 
     TreeNode * left; 
     TreeNode * right; 
     TreeNode( int x) : val( x ), left( NULL ), right( NULL) {} 
 }; 
 
 
 class Solution 
 { 
 public : 
     vector < int > tpr; 
     vector < int > tin; 
     void reBuild( int a , int b , int n , TreeNode * treeNode) 
     { 
         if(n == 1) // leaf node 
         { 
             treeNode = new TreeNode( tpr [ a ]); 
             return ; 
         } 
         else if(n <= 0) // null node 
             return ; 
         int i = 0; 
         for(; tpr [ a ] != tin [b + i ]; ++ i); 
         TreeNode * lson , * rson; 
         reBuild( a + 1 ,b , i , lson); 
         reBuild( a + 1 + i ,b + 1 + i ,n - i - 1 , rson); 
         treeNode = new TreeNode( tpr [ a ]); 
         treeNode -> left = lson; 
         treeNode -> right = rson; 
     } 
     struct TreeNode * reConstructBinaryTree( vector < int > pre , vector < int > in) 
     { 
         tpr . clear(); 
         tin . clear(); 
 
         for( int i = 0; i < pre . size(); ++ i) 
             tpr . push_back( pre [ i ]); 
         for( 