C**5
发帖数: 202 | | C**5
发帖数: 202 | | m**********g
发帖数: 153 | 3 是不是和leetcode的tree deserialization 一样， 不过return判断条件是node level
not equal to current level. Current level 是recursion function 的输入参数
。 | y*******x
发帖数: 40 | 4 似乎可以用stack？
如果当前读到的level等于前一个节点的level+1，则当前节点是前一个节点的左节点。
否则，从栈中重新获取前一个节点，直到满足判断条件，则当前节点是前一个节点的右
节点。最后把当前节点压栈。循环直到栈为空，构建完成。
主要流程的伪代码大致如下（没考虑null等细节）
stack.push(root);
while(!stack.isEmpty()){
read value and level from input.
TreeNode cur = new TreeNode(value,level);
if(cur.level=pre.level+1){
pre.left=cur;
}else{
while(cur.level!=pre.level+1){
pre = stack.pop();
}
pre.right = cur;
}
pre = cur;
stack.push(cur);
} | f********x
发帖数: 2086 | 5
能再稍微解释下题目么？没看懂题
【在 C**5 的大作中提到】
: Help :)
: Is it too easy?
| A*****o
发帖数: 284 | 6 贴个递归的完整代码,抛砖引玉了
#include
#include
#include
#include
using namespace std;
// Interview question: Rebuild a tree with DFS output with level
// A, 0, B, 1, C, 2, D, 2
struct TreeNode {
string id;
TreeNode(string a) {
id = a;
}
vector children;
};
void rebuildImpl(istringstream & iss, TreeNode *&father, string id, int
level) {
TreeNode *p = new TreeNode(id);
if (!father) {
father = p;
}
else {
father->children.push_back(p);
}
string nextId;
int nextLevel;
if (iss >> nextId >> nextLevel) {
if (nextLevel == level) {
rebuildImpl(iss, father, nextId, nextLevel);
}
else { // l == level+1
rebuildImpl(iss, p, nextId, nextLevel);
}
}
}
TreeNode* rebuild(const string &seq) {
istringstream iss(seq);
string id;
int level;
TreeNode *root = NULL;
if (iss >> id >> level) {
rebuildImpl(iss, root, id, level);
}
return root;
}
void dfs(TreeNode *node, int level) {
if (!node) {
return;
}
cout << node->id << " " << level << " ";
for (int i = 0; i < node->children.size(); i++) {
dfs(node->children[i], level+1);
}
}
int main() {
string trail = "A 0 B 1 C 2 D 2";
TreeNode *root = rebuild(trail);
dfs(root, 0); // should print same trail
cout << endl;
return 0;
} | h****t
发帖数: 184 | 7 这个输入怎么能判断B是A的左孩子还是右孩子？
还是说题目的输入本就允许有些情况下 rebuild的tree 不唯一？
【在 C**5 的大作中提到】
: A, 0, B, 1, C, 2, D, 2
| p*****2
发帖数: 21240 | 8
没说是binary tree
【在 h****t 的大作中提到】
: 这个输入怎么能判断B是A的左孩子还是右孩子？
: 还是说题目的输入本就允许有些情况下 rebuild的tree 不唯一？
| p*****2
发帖数: 21240 | 9 rebuild = (arr)->
stack = []
while arr.length > 0
[ch, lv] = arr
if lv is stack.length
node = {val: ch, children:[]}
stack[-1..][0]?.children.push(node)
stack.push(node)
arr = arr[2..]
else
stack.pop()
stack[0] | l*n
发帖数: 529 | 10 可以用hashmap，(K, V)等于(lvl, val)，每次同一层有了新节点就更新hashmap中对应
lvl的元素。下一层减一就能找到他的parent node。
【在 C**5 的大作中提到】
: A, 0, B, 1, C, 2, D, 2
| q****m
发帖数: 177 | 11 没有考虑 nextLevel < level的情况
【在 A*****o 的大作中提到】
: 贴个递归的完整代码,抛砖引玉了
: #include
: #include
: #include
: #include
: using namespace std;
: // Interview question: Rebuild a tree with DFS output with level
: // A, 0, B, 1, C, 2, D, 2
: struct TreeNode {
: string id;
|
|
