问大家一个面试题

2019-09-06 22:56:13 +08:00
 fenghuang

'1(2(3,4(,5)),6(7,))' 把这个字符串转成二叉树

     1
   /   \
  2     6
 / \   / \
3   4 7
     \
      5
5724 次点击
所在节点    程序员
37 条回复
yidinghe
2019-09-06 23:00:16 +08:00
堆栈或者递归
mooyo
2019-09-07 00:31:43 +08:00
递归处理子串
mooyo
2019-09-07 00:32:10 +08:00
@mooyo 迭代不太好做吧
zsdsz
2019-09-07 01:47:16 +08:00
前序遍历
rabbbit
2019-09-07 02:05:24 +08:00
好像写麻烦了...
binux
2019-09-07 03:30:56 +08:00
遇到空或者数字压栈，遇到 ) 弹出 3 个，分别是右左根，把根压回去。over
Mirage09
2019-09-07 06:02:13 +08:00
字符串是 preorder，把字符串先处理成数字和空的队列，然后 preorder 建树，队头如果为空返回空节点，否则新建一个 root 存 queue.poll()，递归建立左子树和右子树。

参考这个： https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/
unionx
2019-09-07 06:16:42 +08:00
这个字符串就已经是二叉树了啊 —— Lisp 程序员
muzhidianzi
2019-09-07 07:01:25 +08:00
小米面试 哈哈哈
Cooky
2019-09-07 07:59:15 +08:00
@unionx 最外层没有括号，不能解析（
geelaw
2019-09-07 08:05:42 +08:00
这是一个非常简单的 DPDA，用一个带有左右孩子和亲代节点指针的结构，从一个单独的根开始。
遇到数字：设置当前节点的值。
遇到左括号：建立并进入左子树。
遇到逗点：回到亲代，如果左子树没有值则删除之，建立并进入右子树。
遇到右括号：回到亲代，如果右子树没有值则删除之。
fenghuang
2019-09-07 08:43:58 +08:00
@rabbbit #5 JS 语法有点看不懂。。。
fenghuang
2019-09-07 08:44:27 +08:00
之前网上看到一个没有逗号，遇到逗号不知道怎么处理
NewDraw
2019-09-07 09:45:39 +08:00
这是一个标准的前序遍历
cassyfar
2019-09-07 09:48:30 +08:00
@binux 优雅
cassyfar
2019-09-07 09:49:39 +08:00
@fenghuang 遇到逗号直接入栈
Lighfer
2019-09-07 09:57:04 +08:00
初始状态默认是根节点
遇到数字，则为当前节点的值
遇到左括号，则进入当前节点的子节点，并默认赋值左子节点
遇到逗号，则切换到右兄弟节点
遇到右括号，则回到当前节点的父节点
所有如果不允许每个节点存储父节点信息，则需要有一个当前节点的父节点栈来记录
fenghuang
2019-09-07 10:04:43 +08:00
@binux #6 试着写一下 谢谢
fenghuang
2019-09-07 10:05:12 +08:00
@cassyfar #16 OK 我试一下
zealot0630
2019-09-07 11:11:45 +08:00
topdown 文法，最容易实现的文法了

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/598732

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX