问大家一个面试题

[fenghuang]

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

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

[yidinghe]

堆栈或者递归

[mooyo]

递归处理子串

[mooyo]

@mooyo 迭代不太好做吧

[zsdsz]

前序遍历

[rabbbit]

好像写麻烦了...

[binux]

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

[Mirage09]

字符串是 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 文法，最容易实现的文法了

[kuanng]

function Tree(data) {
this.data = data
this.lchild = null
this.rchild = null
}
function createTree(data) {
data = data.split('')
let stack = []
let flag = -1
while (data.length) {
let val = data.shift()
if (val === '(') {
if (flag === 0) {
stack.push(stack[stack.length - 1].lchild)
} else if (flag === 1) {
stack.push(stack[stack.length - 1].rchild)
}
flag = 0
} else if (val === ')') {
stack.pop()
} else if (val === ',') {
flag = 1
} else {
let node = new Tree(val)
if (flag === -1) {
root = node
stack.push(node)
} else if (flag === 0) {
stack[stack.length - 1].lchild = node
} else {
stack[stack.length - 1].rchild = node
}
}
}
return root
}

[kuanng]

@kuanng createTree 函数中漏了一行: let root = null

[fenghuang]

大家都喜欢用 js 做题？

[brainfxxk]

我咋觉得这是 LeetCode 原题...

[stevenkang]

这样 OK ？
```js
JSON.parse('{' + ( '1(2(3,4(,5)),6(7,))'.replace(/,\)/g,')').replace(/\(,/g, '(').replace(/\(/g, ':{').replace(/\)/g, '}').replace(/(\d)([,}]{1})/g, '$1:""$2').replace(/(\d)/g, '"$1"') ) + '}')
```

[niubee1]

@unionx 悟空，你又调皮了

[ClarkAbe]

转换成 json 然后按照 json 方式处理😶

[aogu555]

字符串本身已经是前序遍历了

[jaskle]

if(a=='1(2(3,4(,5)),6(7,))'){
1
/ \
2 6
/ \ / \
3 4 7
\
5
}

[shuirong1997]

@rabbbit 啥编辑器？这么简约

[zhengjian]

@shuirong1997 应该是 https://carbon.now.sh/

[normalize]

//12(2(34,4(,5)),6(7,))
//没有测试太多
function treeNode(val) {
this.val = parseInt(val)
this.right = null
this.left = null
}

function stringToTree(str) {
var ary = [] //[1,2,3,4,null,5,6,7]
var re = /\d+/g
re.lastindex = 0
var match

for(var i = 0; i < str.length; i++) {
if(str[i] == ',' && str[i - 1] == '('){
ary.push(null)
}else if(str[i] == ')') {
if(str[i - 1] == ',') {
ary.push(null)
}

var preNode = ary.slice(-3)
ary = ary.slice(0, -3)

preNode[0].left = preNode[1]
preNode[0].right = preNode[2]
ary.push(preNode[0])

}else if(str[i] == '('){
continue
}else if(match = re.exec(str)) {
ary.push(new treeNode(match[0]))
i = match.index + match[0].length - 1
}
}

return ary[0]
}

[jedihy]

不知道有没有 bug

[leafdream]

#11 的思路

[vincenttone]

一个状态机也就搞定了，把开始和结尾换成左右括号会方便很多。也可以是逐个字符读取，靠栈控制就可以完成。lisp 语法本来就是 AST 的表示。

[1608637229]

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* helper(string& s, int i, int j) {
TreeNode* head = nullptr;
if (i > j) return head;
int cur = 0;
while (s[i] >= '0' && s[i] <= '9') {
cur += 10 * cur + s[i] - '0';
++i;
}
head = new TreeNode(cur);
int cnt = 0, k = i + 1;
for (; k < j; ++k) {
if (s[k] == '(') ++cnt;
else if (s[k] == ')') --cnt;
else if (s[k] == ',' && !cnt) break;
}
head->left = helper(s, i + 1, k - 1);
head->right = helper(s, k + 1, j - 1);
return head;
}

TreeNode* trans(string& str) {
if (str.empty()) return nullptr;
return helper(str, 0, str.size() - 1);
}


//先序遍历二叉树
void preOrder(TreeNode* root)
{
if (root == NULL) return;
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}


int main()
{
//测试
string str = "1(2(3,4(,5)),6(7,))";
TreeNode* root = trans(str);
preOrder(root);
cout << endl;
system("pause");
return 0;
}

只能想到暴力了。全部复制过来了，每次都找到那个可以确认分开为左右子树的','.
只测试了通过了这个用例。其他用例我就不知道能不能过了。

[autogen]

#ㅤcoding=utf-8


classㅤBinTreeNode:
ㅤㅤㅤㅤdefㅤ__init__(self,ㅤvalue=None):
ㅤㅤㅤㅤㅤㅤㅤㅤself.valueㅤ=ㅤvalue
ㅤㅤㅤㅤㅤㅤㅤㅤself.leftㅤ=ㅤNone
ㅤㅤㅤㅤㅤㅤㅤㅤself.rightㅤ=ㅤNone
ㅤㅤㅤㅤㅤㅤㅤㅤself.parentㅤ=ㅤNone

ㅤㅤㅤㅤdefㅤaddLeft(self,ㅤnode):
ㅤㅤㅤㅤㅤㅤㅤㅤself.leftㅤ=ㅤnode
ㅤㅤㅤㅤㅤㅤㅤㅤnode.parentㅤ=ㅤself

ㅤㅤㅤㅤdefㅤaddRight(self,ㅤnode):
ㅤㅤㅤㅤㅤㅤㅤㅤself.rightㅤ=ㅤnode
ㅤㅤㅤㅤㅤㅤㅤㅤnode.parentㅤ=ㅤself

ㅤㅤㅤㅤdefㅤ__str__(self):
ㅤㅤㅤㅤㅤㅤㅤㅤstrNodeㅤ=ㅤ"v[%d]"ㅤ%ㅤself.value
ㅤㅤㅤㅤㅤㅤㅤㅤifㅤself.leftㅤisㅤnotㅤNone:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤstrNodeㅤ+=ㅤ"ㅤl[%d]"ㅤ%ㅤself.left.value
ㅤㅤㅤㅤㅤㅤㅤㅤifㅤself.rightㅤisㅤnotㅤNone:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤstrNodeㅤ+=ㅤ"ㅤr[%d]"ㅤ%ㅤself.right.value
ㅤㅤㅤㅤㅤㅤㅤㅤreturnㅤstrNode


classㅤStack:
ㅤㅤㅤㅤdefㅤ__init__(self):
ㅤㅤㅤㅤㅤㅤㅤㅤself.listㅤ=ㅤ[]

ㅤㅤㅤㅤdefㅤpush(self,ㅤdata):
ㅤㅤㅤㅤㅤㅤㅤㅤself.list.append(data)

ㅤㅤㅤㅤdefㅤpop(self):
ㅤㅤㅤㅤㅤㅤㅤㅤdataㅤ=ㅤself.list[-1]
ㅤㅤㅤㅤㅤㅤㅤㅤself.list.pop(-1)
ㅤㅤㅤㅤㅤㅤㅤㅤreturnㅤdata

ㅤㅤㅤㅤdefㅤtop(self):
ㅤㅤㅤㅤㅤㅤㅤㅤifㅤself.empty():
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤreturnㅤNone
ㅤㅤㅤㅤㅤㅤㅤㅤelse:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤreturnㅤself.list[-1]

ㅤㅤㅤㅤdefㅤempty(self):
ㅤㅤㅤㅤㅤㅤㅤㅤreturnㅤlen(self.list)ㅤ==ㅤ0


classㅤBinTreeParser:
ㅤㅤㅤㅤdefㅤ__init__(self,ㅤs):
ㅤㅤㅤㅤㅤㅤㅤㅤself.inStrㅤ=ㅤs
ㅤㅤㅤㅤㅤㅤㅤㅤself.lenStrㅤ=ㅤlen(s)
ㅤㅤㅤㅤㅤㅤㅤㅤself.idxStrㅤ=ㅤ0
ㅤㅤㅤㅤㅤㅤㅤㅤself.rootㅤ=ㅤNone
ㅤㅤㅤㅤㅤㅤㅤㅤself.symbolicㅤ=ㅤ0ㅤㅤ#ㅤ0:num,ㅤ1:openParen,ㅤ2:comma,ㅤ3:closeParen

ㅤㅤㅤㅤdefㅤparseSymbolic(self):
ㅤㅤㅤㅤㅤㅤㅤㅤifㅤself.inStr[self.idxStr]ㅤ==ㅤ'(':
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤself.symbolicㅤ=ㅤ1
ㅤㅤㅤㅤㅤㅤㅤㅤelifㅤself.inStr[self.idxStr]ㅤ==ㅤ',':
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤself.symbolicㅤ=ㅤ2
ㅤㅤㅤㅤㅤㅤㅤㅤelifㅤself.inStr[self.idxStr]ㅤ==ㅤ')':
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤself.symbolicㅤ=ㅤ3
ㅤㅤㅤㅤㅤㅤㅤㅤelse:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤnumㅤ=ㅤ0
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤwhileㅤ'0'ㅤ<=ㅤself.inStr[self.idxStr]ㅤ<=ㅤ'9':
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤnumㅤ*=ㅤ10
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤnumㅤ+=ㅤint(self.inStr[self.idxStr])ㅤ-ㅤint('0')
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤself.idxStrㅤ+=ㅤ1
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤself.symbolicㅤ=ㅤ0
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤreturnㅤnum
ㅤㅤㅤㅤㅤㅤㅤㅤifㅤself.symbolicㅤ!=ㅤ0:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤself.idxStrㅤ+=ㅤ1
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤreturnㅤ0

ㅤㅤㅤㅤdefㅤparse(self):
ㅤㅤㅤㅤㅤㅤㅤㅤrootStackㅤ=ㅤStack()
ㅤㅤㅤㅤㅤㅤㅤㅤcurRootㅤ=ㅤNone
ㅤㅤㅤㅤㅤㅤㅤㅤcurNodeㅤ=ㅤNone
ㅤㅤㅤㅤㅤㅤㅤㅤstateㅤ=ㅤ0

ㅤㅤㅤㅤㅤㅤㅤㅤwhileㅤself.idxStrㅤ<ㅤself.lenStr:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤnumㅤ=ㅤself.parseSymbolic()
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤifㅤself.symbolicㅤ==ㅤ0:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤcurNodeㅤ=ㅤBinTreeNode(num)
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤifㅤstateㅤ==ㅤ1:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤcurRoot.addLeft(curNode)
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤelifㅤstateㅤ==ㅤ2:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤcurRoot.addRight(curNode)
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤelifㅤself.symbolicㅤ==ㅤ1:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤstateㅤ=ㅤ1
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤrootStack.push(curNode)
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤcurRootㅤ=ㅤcurNode
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤifㅤself.rootㅤisㅤNone:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤself.rootㅤ=ㅤcurRoot
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤelifㅤself.symbolicㅤ==ㅤ2:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤstateㅤ=ㅤ2
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤelifㅤself.symbolicㅤ==ㅤ3:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤrootStack.pop()
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤcurRootㅤ=ㅤrootStack.top()
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤstateㅤ=ㅤ3


#ㅤexample:ㅤ'100(200(300,400(,500)),600(700,))'
ifㅤ__name__ㅤ==ㅤ'__main__':
ㅤㅤㅤㅤinStrㅤ=ㅤinput("输入要转换的字符串：")
ㅤㅤㅤㅤparserㅤ=ㅤBinTreeParser(inStr)
ㅤㅤㅤㅤparser.parse()
ㅤㅤㅤㅤprint("pause")





#