- 写在前面
昨天有同学问到我一题关于重构二叉树的问题()，做了一下，也做个记录吧！
所谓二叉树的重构，就是给你前序和中序，或者中序和后序，让你还原这棵二叉树.
注意：给出前序和后序是不能唯一确定一棵二叉树的，.
一.给出前序和中序，重构二叉树
一个递归的过程：
当前结点的value：每一轮根据前序的第一个元素确定当前结点值.
左子树的中序遍历数组：以当前结点的value为分界点，将中序分为左部分和右部分，左部分即为左子树的中序遍历数组.
右子树的中序遍历数组：以当前结点的value为分界点，将中序分为左部分和右部分，右部分即为右子树的中序遍历数组.
左子树的前序遍历数组：pre[1 ... i] (i为左子树的中序遍历数组的个数).
右子树的前序遍历数组：pre[i+1 ... end]（i为左子树的中序遍历数组的个数）.
构造出这5个值，继续递归求左右子树即可.
题目1：
给出前序和中序，要你重建二叉树.
按照上面所说递归即可,详见代码：
/** * ----------------------------------------------------------------- * 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( int i = 0; i < in . size(); ++ i) tin . push_back( in [ i ]); TreeNode * root; int n = pre . size(); reBuild( 0 , 0 ,n , root); return root; } }; void DFS( TreeNode * root) { if( root) { cout <<( root -> val) << " "; } else return ; if( root -> left) DFS( root -> left); if( root -> right) DFS( root -> right); } int main() { freopen( "D: \\ Desktop \\ in.txt" , "r" , stdin); int n; vector < int > pre; vector < int > in; while( cin >>n) { pre . clear(); in . clear(); for( int i = 0; i <n; ++ i) { int tmp; cin >> tmp; pre . push_back( tmp); } for( int i = 0; i <n; ++ i) { int tmp; cin >> tmp; in . push_back( tmp); } Solution a; TreeNode * root = a . reConstructBinaryTree( pre , in); DFS( root); } return 0; }
题目2：
方法一：也很简单，根据上面说的方法递归建树，然后按照后序访问输出即可.
/** * ----------------------------------------------------------------- * Copyright (c) 2016 crazyacking.All rights reserved. * ----------------------------------------------------------------- * Author: crazyacking * Date : 2016-01-04-18.01 */ #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);
int n; vector < int > pr; vector < int > in; struct TreeNode { int val; TreeNode * left , * right; TreeNode( int v) : val( v ), left( NULL ), right( NULL ){} }; TreeNode * reBuildBinaryTree( vector < int > pr , vector < int > in) { if( pr . size() == 0 || in . size() == 0) return NULL; int root = pr [ 0 ]; TreeNode * node = new TreeNode( root); vector < int > prLeft , prRight , inLeft , inRight; int i = 0; for(; pr [ 0 ] != in [ i ]; ++ i); for( int j = 0; j != i; ++ j) inLeft . push_back( in [ j ]); for( int j = i + 1; j < in . size(); ++ j) inRight . push_back( in [ j ]); for( int j = 1; j < i + 1; ++ j) prLeft . push_back( pr [ j ]); for( int j = i + 1; j < pr . size(); ++ j) prRight . push_back( pr [ j ]); node -> left = reBuildBinaryTree( prLeft , inLeft); node -> right = reBuildBinaryTree( prRight , inRight); return node; } vector < int > po; void getPostOrder( TreeNode * root , bool flag) { if( root -> left) getPostOrder( root -> left , 0); if( root -> right) getPostOrder( root -> right , 0); po . push_back( root -> val); } int main() { while( cin >>n) { int tmp; pr . clear(); in . clear(); po . clear(); for( int i = 0; i <n; ++ i) { cin >> tmp; pr . push_back( tmp); } for( int i = 0; i <n; ++ i) { cin >> tmp; in . push_back( tmp); } TreeNode * root = reBuildBinaryTree( pr , in); getPostOrder( root , 1); for( int i = 0; i <n; ++ i) { if( i <n - 1) cout << po [ i ] << " "; else cout << po [ i ] << endl; } } return 0; }
方法二：由于题目没让重构二叉树，只让输出后序访问的顺序，因此可直接访问输出.
/** * ----------------------------------------------------------------- * Copyright (c) 2016 crazyacking.All rights reserved. * ----------------------------------------------------------------- * Author: crazyacking * Date : 2016-01-04-20.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); int n; vector < int > pr; // pre Order vector < int > in; // in Order vector < int > po; // post Order void getPostOrder( int a , int b , int n , bool flag) { if(n == 1) { po . push_back( pr [ a ]); return; } else if(n <= 0) return; int i = 0; for(; pr [ a ] != in [b + i ]; ++ i); getPostOrder( a + 1 ,b , i , false); getPostOrder( a + i + 1 ,b + i + 1 ,n - i - 1 , false); po . push_back( pr [ a ]); } int main() { while( cin >>n) { pr . clear(); in . clear(); po . clear(); for( int i = 0; i <n; ++ i) { int tmp; cin >> tmp; pr . push_back( tmp); } for( int i = 0; i <n; ++ i) { int tmp; cin >> tmp; in . push_back( tmp); } getPostOrder( 0 , 0 ,n , true); for( int i = 0; i <n; ++ i) { if( i <n - 1) cout << po [ i ] << " "; else cout << po [ i ] << endl; } } return 0; }
二.给出后序和中序，重构二叉树
一个递归的过程：
当前结点的value：每一轮根据前序的最后一个元素确定当前结点值.
左子树的中序遍历数组：以当前结点的value为分界点，将中序分为左部分和右部分，左部分即为左子树的中序遍历数组.
右子树的中序遍历数组：以当前结点的value为分界点，将中序分为左部分和右部分，右部分即为右子树的中序遍历数组.
左子树的前序遍历数组：pre[0 ... i-1] (i为左子树的中序遍历数组的个数).
右子树的前序遍历数组：pre[i ... end-1]（i为左子树的中序遍历数组的个数）.
构造出这5个值，继续递归求左右子树即可.
红色部分标出的是和上面的不同点，其余都相同.
/** * ----------------------------------------------------------------- * Copyright (c) 2016 crazyacking.All rights reserved. * ----------------------------------------------------------------- * Author: crazyacking * Date : 2016-01-04-22.07 */ #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); int n; vector < int > po; vector < int > in; struct TreeNode { int val; TreeNode * left , * right; TreeNode( int v) : val( v ), left( NULL ), right( NULL ){} }; TreeNode * reBuildBinaryTree( vector < int > po , vector < int > in) { if( po . size() == 0 || in . size() == 0) return NULL; int root = po [ po . size() - 1 ]; TreeNode * node = new TreeNode( root); vector < int > poLeft , poRight , inLeft , inRight; int i = 0; for(; in [ i ] != root; ++ i); for( int j = 0; j < i; ++ j) inLeft . push_back( in [ j ]); for( int j = i + 1; j < in . size(); ++ j) inRight . push_back( in [ j ]); for( int j = 0; j < i; ++ j) poLeft . push_back( po [ j ]); for( int j = i; j < po . size() - 1; ++ j) poRight . push_back( po [ j ]); node -> left = reBuildBinaryTree( poLeft , inLeft); node -> right = reBuildBinaryTree( poRight , inRight); return node; } void print_BFS( TreeNode * root) { queue < TreeNode *> q; q . push( root); while( ! q . empty()) { TreeNode * now = q . front(); q . pop(); cout <<( now -> val) << " "; if( now -> left) q . push( now -> left); if( now -> right) q . push( now -> right); } } int main() { // test demo int a [] = { 7 , 4 , 2 , 5 , 8 , 6 , 3 , 1 }; int b [] = { 4 , 7 , 2 , 1 , 5 , 3 , 8 , 6 }; po . clear(); in . clear(); for( int i = 0; i < 8; ++ i) { po . push_back( a [ i ]); in . push_back(b [ i ]); } TreeNode * root = reBuildBinaryTree( po , in); print_BFS( root); return 0; }