'1(2(3,4(,5)),6(7,))'
把这个字符串转成二叉树
1
/ \
2 6
/ \ / \
3 4 7
\
5
1
yidinghe 2019-09-06 23:00:16 +08:00 via Android
堆栈或者递归
|
2
mooyo 2019-09-07 00:31:43 +08:00 via Android
递归处理子串
|
4
zsdsz 2019-09-07 01:47:16 +08:00 via Android
前序遍历
|
5
rabbbit 2019-09-07 02:05:24 +08:00
|
6
binux 2019-09-07 03:30:56 +08:00 4
遇到空或者数字压栈,遇到 ) 弹出 3 个,分别是右左根,把根压回去。over
|
7
Mirage09 2019-09-07 06:02:13 +08:00 via iPhone
字符串是 preorder,把字符串先处理成数字和空的队列,然后 preorder 建树,队头如果为空返回空节点,否则新建一个 root 存 queue.poll(),递归建立左子树和右子树。
参考这个: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/ |
8
unionx 2019-09-07 06:16:42 +08:00 7
这个字符串就已经是二叉树了啊 —— Lisp 程序员
|
9
muzhidianzi 2019-09-07 07:01:25 +08:00 via Android
小米面试 哈哈哈
|
11
geelaw 2019-09-07 08:05:42 +08:00 via iPhone 2
这是一个非常简单的 DPDA,用一个带有左右孩子和亲代节点指针的结构,从一个单独的根开始。
遇到数字:设置当前节点的值。 遇到左括号:建立并进入左子树。 遇到逗点:回到亲代,如果左子树没有值则删除之,建立并进入右子树。 遇到右括号:回到亲代,如果右子树没有值则删除之。 |
13
fenghuang OP 之前网上看到一个没有逗号,遇到逗号不知道怎么处理
|
14
NewDraw 2019-09-07 09:45:39 +08:00 via Android
这是一个标准的前序遍历
|
17
Lighfer 2019-09-07 09:57:04 +08:00
初始状态默认是根节点
遇到数字,则为当前节点的值 遇到左括号,则进入当前节点的子节点,并默认赋值左子节点 遇到逗号,则切换到右兄弟节点 遇到右括号,则回到当前节点的父节点 所有如果不允许每个节点存储父节点信息,则需要有一个当前节点的父节点栈来记录 |
20
zealot0630 2019-09-07 11:11:45 +08:00 via Android
topdown 文法,最容易实现的文法了
|
21
kuanng 2019-09-07 12:51:19 +08:00
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 } |
23
fenghuang OP 大家都喜欢用 js 做题?
|
24
brainfxxk 2019-09-07 16:10:16 +08:00
我咋觉得这是 LeetCode 原题...
|
25
stevenkang 2019-09-07 17:31:47 +08:00
这样 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"') ) + '}') ``` ![v2ex1.png]( https://i.loli.net/2019/09/07/cdBSA4xepN7DftZ.png) |
27
ClarkAbe 2019-09-07 20:05:54 +08:00 via Android
转换成 json 然后按照 json 方式处理😶
|
28
aogu555 2019-09-07 20:07:59 +08:00
字符串本身已经是前序遍历了
|
29
jaskle 2019-09-07 20:39:21 +08:00 via Android
if(a=='1(2(3,4(,5)),6(7,))'){
1 / \ 2 6 / \ / \ 3 4 7 \ 5 } |
30
shuirong1997 2019-09-07 21:37:20 +08:00
@rabbbit 啥编辑器?这么简约
|
31
zhengjian 2019-09-07 21:42:00 +08:00
|
32
normalize 2019-09-07 21:47:11 +08:00
//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] } |
33
jedihy 2019-09-08 03:14:24 +08:00 1
|
34
leafdream 2019-09-08 11:03:30 +08:00 1
|
35
vincenttone 2019-09-08 18:40:26 +08:00
一个状态机也就搞定了,把开始和结尾换成左右括号会方便很多。也可以是逐个字符读取,靠栈控制就可以完成。lisp 语法本来就是 AST 的表示。
|
36
1608637229 2019-09-09 15:21:30 +08:00
#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; } 只能想到暴力了。全部复制过来了,每次都找到那个可以确认分开为左右子树的','. 只测试了通过了这个用例。其他用例我就不知道能不能过了。 |
37
autogen 2019-09-11 10:28:03 +08:00
#ㅤ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") # |