S********t
发帖数: 3431 | 1 看似是旧题，你仔细做就知道不是了。跟经典的重健二叉树的题有点类似，但要稍难些。
现在有个树的类，不让你直接知道树的结构，但是有一个visitor可以访问前
序和后序的节点，现在你要写一个你自己的visitor目的是重建树，给你一场面试的时
间你能写吗？
struct Node { ... };
class Tree {
public:
void Walk(TreeVisitor *visitor);
...
};
class TreeVisitor {
public:
virtual ~TreeVisitor();
virtual void PreOrder(const char *node_name, const char *node_value, bool is_leaf) ＝ 0;
virtual void PostOrder(const char *node_name, const char *node_value, bool is_leaf) ＝ 0;
};
现在你要做的是：
1 定义一个你自己的tree data structure (class MyTree)
2 写一个TreeVisitor的subclass来build一个和Tree有同样结构的MyTree |
h**********l
发帖数: 6342 | 2 150原题阿
【在 S********t 的大作中提到】
: 看似是旧题，你仔细做就知道不是了。跟经典的重健二叉树的题有点类似，但要稍难些。
: 现在有个树的类，不让你直接知道树的结构，但是有一个visitor可以访问前
: 序和后序的节点，现在你要写一个你自己的visitor目的是重建树，给你一场面试的时
: 间你能写吗？
: struct Node { ... };
: class Tree {
: public:
: void Walk(TreeVisitor *visitor);
: ...
: };
|
S********t
发帖数: 3431 | 3 没印象啊，我对150应该还是很熟悉，难道150出新版了我不知道？
make sure this problem is regarding generic tree, not BST or binary tree
【在 h**********l 的大作中提到】
: 150原题阿
|
h**********l
发帖数: 6342 | 4 就那个copy一个node，node里面有ptr的阿
用个global map存访问过的
然后recursive call就完了
【在 S********t 的大作中提到】
: 没印象啊，我对150应该还是很熟悉，难道150出新版了我不知道？
: make sure this problem is regarding generic tree, not BST or binary tree
|
S********t
发帖数: 3431 | 5 你这个solution不适用这个题，你再看看题目？我加了些描述
【在 h**********l 的大作中提到】
: 就那个copy一个node，node里面有ptr的阿
: 用个global map存访问过的
: 然后recursive call就完了
|
S********t
发帖数: 3431 | 6 没人做这个？嘿嘿，我下次面人就打算用这题！
些。
【在 S********t 的大作中提到】
: 看似是旧题，你仔细做就知道不是了。跟经典的重健二叉树的题有点类似，但要稍难些。
: 现在有个树的类，不让你直接知道树的结构，但是有一个visitor可以访问前
: 序和后序的节点，现在你要写一个你自己的visitor目的是重建树，给你一场面试的时
: 间你能写吗？
: struct Node { ... };
: class Tree {
: public:
: void Walk(TreeVisitor *visitor);
: ...
: };
|
j****b
发帖数: 108 | 7 这个题不就是给preorder和inorder生成树么？算新题？ |
i**********e
发帖数: 1145 | 8 这题主要考察重建 general tree，不是 binary tree。然后就是怎么把 general tree
用 binary tree 来表示。
还有要注意给的是 preorder 和 postorder.在 binary tree 里 preorder 和
postorder 是不可能重建树的。
不过我认为这题作为面实题，给不到你对 candidate 很有用的signal。个人意见。
【在 j****b 的大作中提到】
: 这个题不就是给preorder和inorder生成树么？算新题？
|
i**********e
发帖数: 1145 | 9 不好意思，可能破坏你这道面试题了。
假设定义为 general tree 的 postorder traversal 是遍历完current node的所有
children再遍历currentnode。
那么主要的trick是要发现 general tree (GT) 的 preorder 跟 binary tree
representation (BTR) 的 preorder 是一样的。另外，GT 的 postorder 和 BTR 的
inorder 遍历也是一样的。
所以重建树就成为了 BTR 的 preorder 和 inorder.
所以这题主要就利用经典的 preorder 和 inorder 遍历重建二叉树，然后再把 BTR 转化成 GT，不知道说对了没有？
http://www.cs.rutgers.edu/~kaplan/503/handouts/btreconNgentrees |
i**********e
发帖数: 1145 | 10 至于怎么把 BTR 转化成 GT 这个过程可以很简单，就看你怎么定义 GT 的 data
structure.
只要把传统二叉树的 left node 定义为 GT 的 first child node，然后 right node
定义为当前 node 的 nextSibling node，就搞定了。这样还省了转化过程。
直接 binary tree preorder 和 inorder 实现一遍就搞定了。 |
S********t
发帖数: 3431 | 11 不行啊，题目的reconstruct意思是要得到一个跟原来的树结构一模一样的树。
而你的方法里面，btr跟gt不等价，所以不可能由一个btr唯一的转换为一个gt
node
【在 i**********e 的大作中提到】
: 至于怎么把 BTR 转化成 GT 这个过程可以很简单，就看你怎么定义 GT 的 data
: structure.
: 只要把传统二叉树的 left node 定义为 GT 的 first child node，然后 right node
: 定义为当前 node 的 nextSibling node，就搞定了。这样还省了转化过程。
: 直接 binary tree preorder 和 inorder 实现一遍就搞定了。
|
S********t
发帖数: 3431 | 12 没说对。。。
转化成 GT，不知道说对了没有？
【在 i**********e 的大作中提到】
: 不好意思，可能破坏你这道面试题了。
: 假设定义为 general tree 的 postorder traversal 是遍历完current node的所有
: children再遍历currentnode。
: 那么主要的trick是要发现 general tree (GT) 的 preorder 跟 binary tree
: representation (BTR) 的 preorder 是一样的。另外，GT 的 postorder 和 BTR 的
: inorder 遍历也是一样的。
: 所以重建树就成为了 BTR 的 preorder 和 inorder.
: 所以这题主要就利用经典的 preorder 和 inorder 遍历重建二叉树，然后再把 BTR 转化成 GT，不知道说对了没有？
: http://www.cs.rutgers.edu/~kaplan/503/handouts/btreconNgentrees
|
