74 lines
2.2 KiB
Markdown
74 lines
2.2 KiB
Markdown
# 毎日一题 - 105.从前序与中序遍历序列构造二叉树
|
||
|
||
## 信息卡片
|
||
|
||
* 时间：2019-08-05
|
||
* 题目链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
|
||
- tag：`Tree` `Array`
|
||
## 题目描述
|
||
```
|
||
根据一棵树的前序遍历与中序遍历构造二叉树。
|
||
|
||
注意:
|
||
你可以假设树中没有重复的元素。
|
||
|
||
例如，给出
|
||
|
||
前序遍历 preorder = [3,9,20,15,7]
|
||
中序遍历 inorder = [9,3,15,20,7]
|
||
返回如下的二叉树：
|
||
|
||
3
|
||
/ \
|
||
9 20
|
||
/ \
|
||
15 7
|
||
```
|
||
## 参考答案
|
||
递归构造二叉树，时间复杂度O(n)
|
||
>
|
||
关键在于前序遍历和中序遍历的特性:
|
||
* 前序遍历：根节点是首元素
|
||
* 中序遍历：根节点左侧的值是其左子树，右侧的值是其右子树
|
||
>
|
||
因此，我们首先要得到从前序序列中获取根节点，然后遍历中序序列，找到根节点的位置，以此直到其左子树和右子树的范围。当我们得到其左子树之后，事情就开始重复了，我们仍然需要根据前序序列中找到这颗左子树的根节点，然后再根据中序序列得到这颗左子树根节点的左右子树，右子树同理。因此实际上就是个回溯。
|
||
```c
|
||
struct TreeNode* _buildTree(int* preorder, int* pindex, int* inorder, int inbegin, int inend)
|
||
{
|
||
if(inbegin>inend)//区间不存在，空树
|
||
{
|
||
return NULL;
|
||
}
|
||
struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
|
||
root->val=preorder[*pindex];
|
||
(*pindex)++;
|
||
if(inbegin==inend)//区间只有一个结点，就是根结点
|
||
{
|
||
root->val=inorder[inbegin];
|
||
root->left=NULL;
|
||
root->right=NULL;
|
||
return root;
|
||
}
|
||
//区间正常
|
||
int rootindex=inbegin;
|
||
while(rootindex<=inend)//用前序的根划分中序为两个子区间
|
||
{
|
||
if(inorder[rootindex]==root->val)
|
||
{
|
||
break;
|
||
}
|
||
else
|
||
{
|
||
++rootindex;
|
||
}
|
||
}
|
||
//递归创建左子树
|
||
root->left= _buildTree(preorder, pindex, inorder, inbegin, rootindex-1);
|
||
//递归创建右子树
|
||
root->right= _buildTree(preorder, pindex, inorder, rootindex+1, inend);
|
||
return root;
|
||
}
|
||
```
|
||
## 其他优秀解答
|
||
|
||
> 暂缺 |