【剑指offer】4-重建二叉树
1-Description
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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) {} };
2-Solution
1- 二叉树的遍历
二叉树是树的一种特殊结构,其每个结点最多只能有2个子结点,以下图的二叉树为例介绍几种主要二叉树遍历的方式:
- 前序遍历:先访问根结点,再访问左子结点,最后访问右子结点,所以遍历顺序为:10-6-4-8-14-12-16
- 中序遍历:先访问左子结点,再访问根结点,最后访问右子结点,所以遍历顺序为:4-6-8-10-12-14-16
- 后续遍历:先访问左子结点,再访问右子结点,最后访问根结点,所以遍历顺序为:4-8-6-12-16-14-10
- 宽度优先遍历:先访问树的第一层结点,再访问第二层结点······一直访问到最下面一层的结点。在同一层结点中,以从左到右的顺序依次访问,所以遍历顺序为:10-6-14-4-8-12-16
2-题目分析
在二叉树的前序遍历序列中,第一个数字总是树的根结点的值。但在中序遍历序列中,根节点的值在序列的中间,左子树的结点的值位于根结点的值得左边。而右子树的结点的值位于根结点的值得右边。可以用下图简单表示:
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin)
{
if(pre.size() == 0 || vin.size() == 0) return NULL;//如果输入无效直接返回NULL
TreeNode* root = new TreeNode(pre[0]);//创建根结点,根节点是前序遍历的第一个数
vector<int>::iterator iter = find(vin.begin(),vin.end(),pre[0]);//找到根结点在中序遍历中的位置
int rootpos = distance(vin.begin(), iter);
vector<int> preleft,vinleft,preright,vinright;
for(int i = 0;i < vin.size();++i){
if(i < rootpos){
vinleft.push_back(vin[i]);
preleft.push_back(pre[i+1]);
}
else if(i>rootpos){
vinright.push_back(vin[i]);
preright.push_back(pre[i]);
}
}
root->left = reConstructBinaryTree(preleft,vinleft);
root->right = reConstructBinaryTree(preright,vinright);
return root;
}
};
通过上面的代码,如果输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},可以运行得到下面的结果:
PS:公众号上线啦,技术干货分享,欢迎关注。