一、题目描述
二、解题思路
- 先修概念
- 这道题只能用递归来做，重点是怎么在两个序列里确定左右子树的区间
- 由上一步的思路，这两个区间需要用户去指定
- 前序遍历：NLR；中序遍历：LNR
- 递归前的准备工作
- 首先，给定的前序遍历的区间段，我们可以知道当前正在创建的子树的头结点：前序遍历区间最左的元素
- 其次，我们需要找到这个元素为于中序遍历区间的何处：从中序遍历区间最左遍历到区间最右，相等证明找到，记录下标
- 于是，在中序遍历序列的当前区间里，我们知道了左右子树的区间长度
- 接下来就是怎么递归创建左右子树的问题，也就是怎么递归确定左右子树区间的问题
- 左子树
- 如果左子树区间长度为0，说明左子树为空
- 否则，由前序遍历的NLR和中序遍历的LNR
- 前序遍历序列
- 左子树的区间起点为传入的起始点
pl的下一个位置，再由左子树长度可以推知左子树的区间终点
- 左子树的区间起点为传入的起始点
- 中序遍历序列
- 左子树的区间起点为传入的起始点
il，再由左子树长度可以推知左子树的区间终点
- 左子树的区间起点为传入的起始点
- 前序遍历序列
- 右子树
- 如果右子树区间长度为0，说明右子树为空
- 否则，由前序遍历的NLR和中序遍历的LNR
- 前序遍历序列
- 右子树的区间起点为左子树区间终点的下一个位置；由NLR性质，终点即为传入的
pr
- 右子树的区间起点为左子树区间终点的下一个位置；由NLR性质，终点即为传入的
- 中序遍历序列
- 右子树的区间起点为起始点；由LNR性质，终点即为传入的
ir
- 右子树的区间起点为起始点；由LNR性质，终点即为传入的
- 前序遍历序列
- 左子树
三、解题代码
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(!preorder.size() || !inorder.size()) return nullptr;
return MyCreate(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
private:
TreeNode* MyCreate(vector<int>& preorder, unsigned int pl, unsigned int pr, vector<int>& inorder, unsigned int il, unsigned int ir) {
auto Cur_Head = new TreeNode(preorder[pl]);
unsigned int find_il; //在中序遍历的序列里找到和头结点值相同的位置，这个位置划分了头结点的左右子树
for(find_il = il; inorder[find_il] != Cur_Head->val; find_il++);
auto LeftTreeLen = find_il - il;
auto RightTreeLen = ir - find_il;
if(LeftTreeLen)
Cur_Head->left = MyCreate(preorder, pl + 1, pl + LeftTreeLen, inorder, il, il + LeftTreeLen - 1);
else
Cur_Head->left = nullptr;
if(RightTreeLen)
Cur_Head->right = MyCreate(preorder, pl + LeftTreeLen + 1, pr, inorder, find_il + 1, ir);
else
Cur_Head->right = nullptr;
return Cur_Head;
}
};
四、测试数据
可以用这组来试试
[1,5,6,8,20,31,3,7,42,9,8,2]
[5,20,8,31,6,1,7,3,9,2,8,42]
[1,5,3,null,6,7,42,8,null,null,null,9,null,20,31,null,8,null,null,null,null,2]
京公网安备 11010502036488号