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;
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
## 其他优秀解答
|
|||
|
|
|
|||
|
|
> 暂缺
|