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

问大家一个面试题

  •  
  •   fenghuang · 93 天前 · 4467 次点击
    这是一个创建于 93 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

         1
       /   \
      2     6
     / \   / \
    3   4 7
         \
          5
    
    37 回复  |  直到 2019-09-11 10:28:03 +08:00
        1
    yidinghe   93 天前 via Android
    堆栈或者递归
        2
    mooyo   93 天前 via Android
    递归处理子串
        3
    mooyo   93 天前 via Android
    @mooyo 迭代不太好做吧
        4
    zsdsz   93 天前 via Android
    前序遍历
        5
    rabbbit   93 天前
    好像写麻烦了...
        6
    binux   93 天前   ♥ 4
    遇到空或者数字压栈,遇到 ) 弹出 3 个,分别是右左根,把根压回去。over
        7
    Mirage09   93 天前 via iPhone
    字符串是 preorder,把字符串先处理成数字和空的队列,然后 preorder 建树,队头如果为空返回空节点,否则新建一个 root 存 queue.poll(),递归建立左子树和右子树。

    参考这个: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/
        8
    unionx   93 天前   ♥ 7
    这个字符串就已经是二叉树了啊 —— Lisp 程序员
        9
    muzhidianzi   93 天前 via Android
    小米面试 哈哈哈
        10
    Cooky   93 天前 via Android
    @unionx 最外层没有括号,不能解析(
        11
    geelaw   93 天前 via iPhone   ♥ 2
    这是一个非常简单的 DPDA,用一个带有左右孩子和亲代节点指针的结构,从一个单独的根开始。
    遇到数字:设置当前节点的值。
    遇到左括号:建立并进入左子树。
    遇到逗点:回到亲代,如果左子树没有值则删除之,建立并进入右子树。
    遇到右括号:回到亲代,如果右子树没有值则删除之。
        12
    fenghuang   93 天前
    @rabbbit #5 JS 语法有点看不懂。。。
        13
    fenghuang   93 天前
    之前网上看到一个没有逗号,遇到逗号不知道怎么处理
        14
    NewDraw   93 天前 via Android
    这是一个标准的前序遍历
        15
    cassyfar   93 天前
    @binux 优雅
        16
    cassyfar   93 天前
    @fenghuang 遇到逗号直接入栈
        17
    Lighfer   93 天前
    初始状态默认是根节点
    遇到数字,则为当前节点的值
    遇到左括号,则进入当前节点的子节点,并默认赋值左子节点
    遇到逗号,则切换到右兄弟节点
    遇到右括号,则回到当前节点的父节点
    所有如果不允许每个节点存储父节点信息,则需要有一个当前节点的父节点栈来记录
        18
    fenghuang   93 天前
    @binux #6 试着写一下 谢谢
        19
    fenghuang   93 天前
    @cassyfar #16 OK 我试一下
        20
    zealot0630   93 天前 via Android
    topdown 文法,最容易实现的文法了
        21
    kuanng   93 天前
    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
    }
        22
    kuanng   93 天前
    @kuanng createTree 函数中漏了一行: let root = null
        23
    fenghuang   93 天前
    大家都喜欢用 js 做题?
        24
    brainfxxk   93 天前
    我咋觉得这是 LeetCode 原题...
        25
    stevenkang   93 天前
    这样 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)
        26
    niubee1   93 天前
    @unionx 悟空,你又调皮了
        27
    ClarkAbe   92 天前 via Android
    转换成 json 然后按照 json 方式处理😶
        28
    aogu555   92 天前
    字符串本身已经是前序遍历了
        29
    jaskle   92 天前 via Android
    if(a=='1(2(3,4(,5)),6(7,))'){
    1
    / \
    2 6
    / \ / \
    3 4 7
    \
    5
    }
        30
    shuirong1997   92 天前
    @rabbbit 啥编辑器?这么简约
        31
    zhengjian   92 天前
        32
    normalize   92 天前
    //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   92 天前   ♥ 1
    不知道有没有 bug

        34
    leafdream   92 天前   ♥ 1
    #11 的思路

        35
    vincenttone   92 天前
    一个状态机也就搞定了,把开始和结尾换成左右括号会方便很多。也可以是逐个字符读取,靠栈控制就可以完成。lisp 语法本来就是 AST 的表示。
        36
    1608637229   91 天前
    #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   89 天前
    #ㅤ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")





    #
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2999 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 26ms · UTC 11:33 · PVG 19:33 · LAX 03:33 · JFK 06:33
    ♥ Do have faith in what you're doing.