问大家一个面试题

[fenghuang]

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

     1
   /   \
  2     6
 / \   / \
3   4 7
     \
      5

[yidinghe]

堆栈或者递归

[mooyo]

递归处理子串

[mooyo]

@mooyo 迭代不太好做吧

[zsdsz]

前序遍历

[rabbbit]

好像写麻烦了...

[binux]

遇到空或者数字压栈，遇到 ) 弹出 3 个，分别是右左根，把根压回去。over

[NVDA]

字符串是 preorder，把字符串先处理成数字和空的队列，然后 preorder 建树，队头如果为空返回空节点，否则新建一个 root 存 queue.poll()，递归建立左子树和右子树。

参考这个： https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

[unionx]

这个字符串就已经是二叉树了啊 —— Lisp 程序员

[muzhidianzi]

小米面试 哈哈哈

[Cooky]

@unionx 最外层没有括号，不能解析（

[geelaw]

这是一个非常简单的 DPDA，用一个带有左右孩子和亲代节点指针的结构，从一个单独的根开始。
遇到数字：设置当前节点的值。
遇到左括号：建立并进入左子树。
遇到逗点：回到亲代，如果左子树没有值则删除之，建立并进入右子树。
遇到右括号：回到亲代，如果右子树没有值则删除之。

[fenghuang]

@rabbbit #5 JS 语法有点看不懂。。。

[fenghuang]

之前网上看到一个没有逗号，遇到逗号不知道怎么处理

[NewDraw]

这是一个标准的前序遍历

[cassyfar]

@binux 优雅

[cassyfar]

@fenghuang 遇到逗号直接入栈

[Lighfer]

初始状态默认是根节点
遇到数字，则为当前节点的值
遇到左括号，则进入当前节点的子节点，并默认赋值左子节点
遇到逗号，则切换到右兄弟节点
遇到右括号，则回到当前节点的父节点
所有如果不允许每个节点存储父节点信息，则需要有一个当前节点的父节点栈来记录

[fenghuang]

@binux #6 试着写一下 谢谢

[fenghuang]

@cassyfar #16 OK 我试一下

[zealot0630]

topdown 文法，最容易实现的文法了