V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
fenghuang
V2EX  ›  程序员

问大家一个面试题

  •  
  •   fenghuang · 2019-09-06 22:56:13 +08:00 · 5464 次点击
    这是一个创建于 1665 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

         1
       /   \
      2     6
     / \   / \
    3   4 7
         \
          5
    
    37 条回复    2019-09-11 10:28:03 +08:00
    yidinghe
        1
    yidinghe  
       2019-09-06 23:00:16 +08:00 via Android
    堆栈或者递归
    mooyo
        2
    mooyo  
       2019-09-07 00:31:43 +08:00 via Android
    递归处理子串
    mooyo
        3
    mooyo  
       2019-09-07 00:32:10 +08:00 via Android
    @mooyo 迭代不太好做吧
    zsdsz
        4
    zsdsz  
       2019-09-07 01:47:16 +08:00 via Android
    前序遍历
    rabbbit
        5
    rabbbit  
       2019-09-07 02:05:24 +08:00
    好像写麻烦了...
    binux
        6
    binux  
       2019-09-07 03:30:56 +08:00   ❤️ 4
    遇到空或者数字压栈,遇到 ) 弹出 3 个,分别是右左根,把根压回去。over
    Mirage09
        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/
    unionx
        8
    unionx  
       2019-09-07 06:16:42 +08:00   ❤️ 7
    这个字符串就已经是二叉树了啊 —— Lisp 程序员
    muzhidianzi
        9
    muzhidianzi  
       2019-09-07 07:01:25 +08:00 via Android
    小米面试 哈哈哈
    Cooky
        10
    Cooky  
       2019-09-07 07:59:15 +08:00 via Android
    @unionx 最外层没有括号,不能解析(
    geelaw
        11
    geelaw  
       2019-09-07 08:05:42 +08:00 via iPhone   ❤️ 2
    这是一个非常简单的 DPDA,用一个带有左右孩子和亲代节点指针的结构,从一个单独的根开始。
    遇到数字:设置当前节点的值。
    遇到左括号:建立并进入左子树。
    遇到逗点:回到亲代,如果左子树没有值则删除之,建立并进入右子树。
    遇到右括号:回到亲代,如果右子树没有值则删除之。
    fenghuang
        12
    fenghuang  
    OP
       2019-09-07 08:43:58 +08:00
    @rabbbit #5 JS 语法有点看不懂。。。
    fenghuang
        13
    fenghuang  
    OP
       2019-09-07 08:44:27 +08:00
    之前网上看到一个没有逗号,遇到逗号不知道怎么处理
    NewDraw
        14
    NewDraw  
       2019-09-07 09:45:39 +08:00 via Android
    这是一个标准的前序遍历
    cassyfar
        15
    cassyfar  
       2019-09-07 09:48:30 +08:00
    @binux 优雅
    cassyfar
        16
    cassyfar  
       2019-09-07 09:49:39 +08:00
    @fenghuang 遇到逗号直接入栈
    Lighfer
        17
    Lighfer  
       2019-09-07 09:57:04 +08:00
    初始状态默认是根节点
    遇到数字,则为当前节点的值
    遇到左括号,则进入当前节点的子节点,并默认赋值左子节点
    遇到逗号,则切换到右兄弟节点
    遇到右括号,则回到当前节点的父节点
    所有如果不允许每个节点存储父节点信息,则需要有一个当前节点的父节点栈来记录
    fenghuang
        18
    fenghuang  
    OP
       2019-09-07 10:04:43 +08:00
    @binux #6 试着写一下 谢谢
    fenghuang
        19
    fenghuang  
    OP
       2019-09-07 10:05:12 +08:00
    @cassyfar #16 OK 我试一下
    zealot0630
        20
    zealot0630  
       2019-09-07 11:11:45 +08:00 via Android
    topdown 文法,最容易实现的文法了
    kuanng
        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
    }
    kuanng
        22
    kuanng  
       2019-09-07 12:54:38 +08:00
    @kuanng createTree 函数中漏了一行: let root = null
    fenghuang
        23
    fenghuang  
    OP
       2019-09-07 15:30:33 +08:00
    大家都喜欢用 js 做题?
    brainfxxk
        24
    brainfxxk  
       2019-09-07 16:10:16 +08:00
    我咋觉得这是 LeetCode 原题...
    stevenkang
        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)
    niubee1
        26
    niubee1  
       2019-09-07 18:07:00 +08:00
    @unionx 悟空,你又调皮了
    ClarkAbe
        27
    ClarkAbe  
       2019-09-07 20:05:54 +08:00 via Android
    转换成 json 然后按照 json 方式处理😶
    aogu555
        28
    aogu555  
       2019-09-07 20:07:59 +08:00
    字符串本身已经是前序遍历了
    jaskle
        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
    }
    shuirong1997
        30
    shuirong1997  
       2019-09-07 21:37:20 +08:00
    @rabbbit 啥编辑器?这么简约
    zhengjian
        31
    zhengjian  
       2019-09-07 21:42:00 +08:00
    normalize
        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]
    }
    jedihy
        33
    jedihy  
       2019-09-08 03:14:24 +08:00   ❤️ 1
    不知道有没有 bug

    leafdream
        34
    leafdream  
       2019-09-08 11:03:30 +08:00   ❤️ 1
    #11 的思路

    vincenttone
        35
    vincenttone  
       2019-09-08 18:40:26 +08:00
    一个状态机也就搞定了,把开始和结尾换成左右括号会方便很多。也可以是逐个字符读取,靠栈控制就可以完成。lisp 语法本来就是 AST 的表示。
    1608637229
        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;
    }

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





    #
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5361 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 42ms · UTC 07:31 · PVG 15:31 · LAX 00:31 · JFK 03:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.