问题描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
算法分析
算法的基本思路是分治法,divide and conquer,可以拆解这个为相似的小问题,pre的第一个元素是根节点,树或者子树,然后可以拆解为左右子树的pre和vin,进行同样的过程
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
|
class Solution { public: TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { if (pre.size() == 0) return NULL; else if (pre.size() == 1){ TreeNode* root = new TreeNode(pre.back()); root -> left = NULL; root -> right = NULL; return root; } else { TreeNode* root = new TreeNode(pre.at(0)); vector<int>::iterator it = vin.begin(); while(it != vin.end() && *it != pre.at(0)) ++it; int dis = it - vin.begin(); vector<int> subPreLeft(pre.begin() + 1, pre.begin() + dis + 1); vector<int> subPreRight(pre.begin() + dis + 1, pre.end()); vector<int> subVinLeft(vin.begin(), it); vector<int> subVinRight(it + 1, vin.end() ); root -> left = reConstructBinaryTree(subPreLeft, subVinLeft); root -> right = reConstructBinaryTree(subPreRight, subVinRight); return root; } } };
|