题目链接:Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
这道题的要求是通过二叉树的前序遍历和中序遍历结果构建二叉树。
二叉树前序遍历,根节点在最前面,然后接下来是左子树、右子数的节点;二叉树中序遍历,根节点在中间,左侧是左子树的节点,右侧是右子树的节点。由此可以确定,前序遍历的第一个节点就是根节点,而中序遍历中和前序遍历的第一个节点相同的同样为根节点,同时左侧即为左子树,右侧即为右子数。至于左右子树的情况,可以通过递归生成。
例如:
二叉树为:
1
/ \
2 3
/ \ \
4 5 6
前序遍历:
1 -> 2 -> 4 -> 5 -> 3 -> 6
| |---------| |----|
根节点 左子树 右子数
中序遍历:
4 -> 2 -> 5 -> 1 -> 3 -> 6
|---------| | |----|
左子树 根节点 右子数
分别在前序遍历和中序遍历中找到了根节点和左右子树,接下来就可以构建这棵树了。
时间复杂度:O(n)
空间复杂度:O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
{
return buildTree(preorder, 0, preorder.size() - 1,
inorder, 0, inorder.size() - 1);
}
private:
// preorder:前序遍历的序列;pl和pr:前序遍历序列中树的左右端点;
// inorder:中序遍历的序列;il和ir:中序遍历序列中树的左右端点。
TreeNode *buildTree(vector<int> &preorder, int pl, int pr,
vector<int> &inorder, int il, int ir)
{
if(pl > pr && il > ir)
return NULL;
int m;
// 在中序遍历序列中找到根节点位置
for(m = il; m <= ir && preorder[pl] != inorder[m]; ++ m);
TreeNode *t = new TreeNode(preorder[pl]);
t->left = buildTree(preorder, pl + 1, pl + m - il,
inorder, il, m - 1);
t->right = buildTree(preorder, pl + m - il + 1, pr,
inorder, m + 1, ir);
return t;
}
};