2014-05-08 08:26
原题：
Given a preorder traversal, create a binary search tree in optimized time
题目：给定一个二叉搜索树的前序遍历，请重建这棵树。要求最优化算法。
解法1：这人每次出题都要求“最优算法”，自己写的代码却实在让人汗颜，让人觉得这家伙就是懒得思考，想从别人那儿问答案。前序遍历的顺序是“根左右”，那么根节点之后所有小于根的部分就是左子树，后面就是右子树了。怎么找这条分界线呢？可以顺着找。那么算法的复杂度就是O(n * log(n))了。复杂度的证明参考归并排序即可。这个算法可行，但不是最优。
代码：
// http://www.careercup.com/question?id=5162732873580544
#include <iostream>
#include <vector>
using namespace std; struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int _val = ): val(_val), left(nullptr), right(nullptr) {};
}; void constructBSTFromPreorderTraversal(vector<int> &v, int ll, int rr, TreeNode *&root)
{
root = new TreeNode(v[ll]); int i = ll + ;
while (i <= rr && v[i] < v[ll]) {
++i;
}
if (ll + <= i - ) {
constructBSTFromPreorderTraversal(v, ll + , i - , root->left);
}
if (i <= rr) {
constructBSTFromPreorderTraversal(v, i, rr, root->right);
}
} void inorderTraversal(TreeNode *root)
{
if (nullptr == root) {
return;
}
inorderTraversal(root->left);
cout << root->val << ' ';
inorderTraversal(root->right);
} void clearTree(TreeNode *&root)
{
if (nullptr == root) {
return;
}
clearTree(root->left);
clearTree(root->right);
delete root;
root = nullptr;
} int main()
{
vector<int> v;
int n;
int i;
TreeNode *root; while (cin >> n && n > ) {
v.resize(n);
for (i = ; i < n; ++i) {
cin >> v[i];
}
root = nullptr;
constructBSTFromPreorderTraversal(v, , n - , root);
inorderTraversal(root);
cout << endl; clearTree(root);
v.clear();
} return ;
}
解法2：既然遍历是O(n)时间完成的，重建应该也可以做到O(n)。我的思路，是比较三个节点的值：父节点，当前节点，新节点。根据它们之间的大小关系可以判断新的节点应该插入在哪儿。代码中的关键部分很短，所以不需要多余解释了。其中用到了一个节点栈，用于回溯。所以这个算法用递归来写也是同样直观的。
// http://www.careercup.com/question?id=5162732873580544
#include <iostream>
#include <vector>
using namespace std; struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int _val = ): val(_val), left(nullptr), right(nullptr) {};
}; void inorderTraversal(TreeNode *root)
{
if (nullptr == root) {
return;
}
inorderTraversal(root->left);
cout << root->val << ' ';
inorderTraversal(root->right);
} void clearTree(TreeNode *&root)
{
if (nullptr == root) {
return;
}
clearTree(root->left);
clearTree(root->right);
delete root;
root = nullptr;
} int main()
{
vector<int> v;
int n;
int i;
TreeNode *root;
TreeNode *tmp;
vector<TreeNode *> st; while (cin >> n && n > ) {
v.resize(n);
for (i = ; i < n; ++i) {
cin >> v[i];
} root = new TreeNode(v[]);
st.push_back(root);
for (i = ; i < n; ++i) {
if (v[i] < st[st.size() - ]->val) {
tmp = new TreeNode(v[i]);
st[st.size() - ]->left = tmp;
st.push_back(tmp);
} else if (st.size() == || v[i] < st[st.size() - ]->val) {
tmp = new TreeNode(v[i]);
st[st.size() - ]->right = tmp;
st.push_back(tmp);
} else {
st.pop_back();
--i;
}
} inorderTraversal(root);
cout << endl; v.clear();
st.clear();
clearTree(root);
} return ;
}