google 面经

codinggiving a string of tree nodes

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

reconstruct the tree

楼主题目说得不是很清楚, 我说说我的理解吧
题目可以叫 reconstruct tree given preorder traversal of treeNodes with the number of children.

[3, 3, 1, 0, 2, 1, 4, 0, 5, 0] 大概表示的是下面这个tree:
             3
     1      2     5
             4

解法应该是用stack记录每一层的节点以及需要添加的子节点个数, 遇到新的节点就加到栈顶的子节点列表里, 如果自己也需要子节点, 就放到栈顶. 每当栈顶的节点加够了子节点就pop出来, 最后返回根节点.

以上纯粹猜测

求问楼主，两个3后面的1是什么呢？是child的值，还是另一个root？
e.g. root, children.size(), child1, child2, child3, x, y, z 吗？那么后面的x, y, z分别是child1的children.size()及childrens吗？
还是e.g. root1, children_root1.size(), child1, child2, child3, root2, children_root2.size(), child1, child2, child3?

谢谢楼主！

补充内容 (2017-11-15 09:07):
我猜肯定是第一种..第二种有点太简单了..

lz能再稍微详细的说下这个string里node是怎么分部的嘛？。。感觉有不少可能性。。感谢！