问大家一个面试题

堆栈或者递归

递归处理子串

@mooyo 迭代不太好做吧

前序遍历

好像写麻烦了...

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

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

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

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

小米面试 哈哈哈

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

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

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

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

这是一个标准的前序遍历

@binux 优雅

@fenghuang 遇到逗号直接入栈

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

@binux #6 试着写一下 谢谢

@cassyfar #16 OK 我试一下

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

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 createTree 函数中漏了一行: let root = null

大家都喜欢用 js 做题？

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

这样 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"') ) + '}')
```

@unionx 悟空，你又调皮了

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

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

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

@rabbbit 啥编辑器？这么简约

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

//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]
}

不知道有没有 bug

#11 的思路

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

#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;
}

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

#coding=utf-8


classBinTreeNode:
def__init__(self,value=None):
self.value=value
self.left=None
self.right=None
self.parent=None

defaddLeft(self,node):
self.left=node
node.parent=self

defaddRight(self,node):
self.right=node
node.parent=self

def__str__(self):
strNode="v[%d]"%self.value
ifself.leftisnotNone:
strNode+="l[%d]"%self.left.value
ifself.rightisnotNone:
strNode+="r[%d]"%self.right.value
returnstrNode


classStack:
def__init__(self):
self.list=[]

defpush(self,data):
self.list.append(data)

defpop(self):
data=self.list[-1]
self.list.pop(-1)
returndata

deftop(self):
ifself.empty():
returnNone
else:
returnself.list[-1]

defempty(self):
returnlen(self.list)==0


classBinTreeParser:
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

defparseSymbolic(self):
ifself.inStr[self.idxStr]=='(':
self.symbolic=1
elifself.inStr[self.idxStr]==',':
self.symbolic=2
elifself.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
returnnum
ifself.symbolic!=0:
self.idxStr+=1
return0

defparse(self):
rootStack=Stack()
curRoot=None
curNode=None
state=0

whileself.idxStr<self.lenStr:
num=self.parseSymbolic()
ifself.symbolic==0:
curNode=BinTreeNode(num)
ifstate==1:
curRoot.addLeft(curNode)
elifstate==2:
curRoot.addRight(curNode)
elifself.symbolic==1:
state=1
rootStack.push(curNode)
curRoot=curNode
ifself.rootisNone:
self.root=curRoot
elifself.symbolic==2:
state=2
elifself.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")





#