【算法入门06】重建二叉树

【算法入门06】重建二叉树

核心考点：二叉树重建，遍历理解，递归

给定某二叉树的前序遍历和中序遍历，且前序遍历和中序遍历当中无重复元素，请重建出该二叉树并返回它的头结点。例如输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建出的二叉树如下图所示。

解析：

首先我们必须知道前序遍历和中序遍历的遍历顺序：

前序遍历顺序：根 -> 左子树 -> 右子树 中序遍历顺序：左子树 -> 根 -> 右子树

据此我们可以知道，前序遍历序列的第一个数字一定是二叉树的根结点。得到了根结点的值后，我们就可以在中序遍历当中找到根结点的位置。

因为中序遍历的顺序是：左子树 -> 根 -> 右子树，所以此时根结点的左边便是左子树的中序遍历序列，根结点的右边便是右子树的中序遍历序列。

而且我们还可以根据根结点在中序遍历序列当中的下标，计算出左子树的结点个数和右子树的结点个数，并据此得到左子树的前序遍历序列和右子树的前序遍历序列。

此时，根据前序遍历序列和中序遍历序列重建二叉树的问题就变成了，根据左子树前序遍历序列和中序遍历序列重建左子树，以及根据右子树前序遍历序列和中序遍历序列重建右子树了。而我们可以用相同的方法去进行重建，直至子树的前序序列以及中序序列不存在，此时二叉树也就重建好了。

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: TreeNode* reConstructBinaryTree(vector pre, vector vin) { if (pre.empty() || vin.empty() || pre.size() != vin.size()) //前序遍历序列为空，中序遍历序列为空，前序中序遍历序列中数字个数不同，则非法 return nullptr; //递归创建二叉树并返回根结点地址 return _reConstructBinaryTree(pre, 0, pre.size() - 1, vin, 0, vin.size() - 1); } TreeNode* _reConstructBinaryTree(vector pre, int PreStart, int PreEnd, vector vin, int VinStart, int VinEnd) { //树的前序遍历序列或中序遍历序列不存在（递归结束条件） if (PreStart > PreEnd || VinStart > VinEnd) { return nullptr; } TreeNode* root = new TreeNode(pre[PreStart]); //创建根结点 for (int i = VinStart; i <= VinEnd; i++) { if (vin[i] == pre[PreStart]) //在所给中序序列当中找到根结点 { //递归创建左子树 root->left = _reConstructBinaryTree(pre, PreStart + 1, PreStart + i - VinStart, vin, VinStart, i - 1); //递归创建右子树 root->right = _reConstructBinaryTree(pre, PreStart + i - VinStart + 1, PreEnd, vin, i + 1, VinEnd); break; } } return root; //返回根结点地址 }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。