想起一道经典的408题，层序遍历、前序遍历、中序遍历、后序遍历四种遍历方法两两组合，哪个组合不能确定一个二叉树？
答案显然是前序遍历和后序遍历组合。
这里要实现的就是，从前序与中序遍历序列构造二叉树。
方法很简单：把遍历分成左子树、根和右子树，再分别把左右子树递归。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
TreeNode* node = new TreeNode(preorder[0]);
if(preorder.size() == 1)
return node;
int left = find(inorder.begin(),inorder.end(),preorder[0]) - inorder.begin();
if(left != 0)
{
vector<int> pre(preorder.begin() + 1, preorder.begin() + 1 + left);
vector<int> ino(inorder.begin(),inorder.begin() + left);
node->left = buildTree(pre, ino);
}
if(left + 1 != preorder.size())
{
vector<int> pre(preorder.begin() + 1 + left, preorder.end());
vector<int> ino(inorder.begin() + left + 1, inorder.end());
node->right = buildTree(pre, ino);
}
return node;
}
};
|