字节跳动2-1 20210324电商面试，根据字符串输出二插树结构

分手后的思念是犯贱 2022-11-13 04:11 100阅读 0赞

解析形如A(B(C(,D(F,G)),),E(,))的字符串，在内存中构建一棵二叉树。

1.A(B(C(,D(F,G)),),E(,)) 对应的二叉树如下图所示：

A  
  B   E  
C    
  D  
 F  G

2.代码实现 (第一种判断分开式方式)

public class TreeTest {
        public static void main(String[] args) {
    
            String nodeStr = "A(B(C(,),),E(,))";
    
            TreeTest treeTest = new TreeTest();
            StringTreeNode stringTreeNode = treeTest.getStringTreeNodeByString2(nodeStr);
            System.out.println(stringTreeNode);
        }
    
        public StringTreeNode getStringTreeNodeByString2(String nodeStr){
            StringTreeNode returnNode = null;
            try {
                StringTreeNode parentNode = null;
                StringTreeNode currentNode = null;
                Character preChar = null;
                for (int i = 0; i < nodeStr.length(); i++) {
                    Character character = nodeStr.charAt(i);
                    if (parentNode == null && 'A' <= character && character <= 'Z') {
                        StringTreeNode stringTreeNode = new StringTreeNode(null, character);
                        returnNode = stringTreeNode;
                        parentNode = stringTreeNode;
                        currentNode = stringTreeNode;
                        preChar = character;
                        continue;
                    }
    
                    //左节点
                    if (preChar.equals('(') && 'A' <= character && character <= 'Z') {
                        StringTreeNode stringTreeNode = new StringTreeNode(parentNode, character);
                        parentNode.leftNode = stringTreeNode;
                        currentNode = stringTreeNode;
                    }
    
                    //右节点
                    if (preChar.equals(',') && 'A' <= character && character <= 'Z') {
                        StringTreeNode stringTreeNode = new StringTreeNode(parentNode, character);
                        parentNode.rightNode = stringTreeNode;
                        currentNode = stringTreeNode;
                    }
    
                    //是否下降
                    if ('A' <= preChar && preChar <= 'Z' && character.equals('(')) {
                        parentNode = currentNode;
                    }
    
                    //是否回撤
                    if (character.equals(')')) {
                        parentNode = parentNode.parentNode;
                    }
                    preChar = character;
                }
            }catch (Exception e){
                e.printStackTrace();
            }
    
            return returnNode;
        }
    
    
    
    }
    
    
    class StringTreeNode{
    
        public StringTreeNode parentNode;
        public StringTreeNode leftNode;
        public StringTreeNode rightNode;
    
        public Character value;
    
        public StringTreeNode(StringTreeNode parentNode,Character value){
            this.parentNode = parentNode;
            this.value = value;
        }
    }

第二种方式(集中式判断方式这种方式判断数据逻辑性更强)

package jieduaner;
    
    public class StringReadTree {
        public static void main(String[] args) {
            StringReadTree stringReadTree = new StringReadTree();
    
            String s = "A(B(C(,D(F,G)),),E(,))";
    
            StringNode stringNode = stringReadTree.getTree(s);
    
            System.out.println(stringNode);
        }
    
        public StringNode getTree(String str){
            StringNode returnNode = null;
    
            int index =0;
            StringNode rootStringNode = null;
            StringNode preStringNode = null;
            Character preCharecter = null;
            while(index<str.length()){
                //获取当前字符
                char c = str.charAt(index);
                StringNode stringNode;
                if('A'<=c&& c<'Z') {
                    stringNode = new StringNode();
                    stringNode.value = c;
                    if (preCharecter != null && preCharecter == ',') {
                        if (rootStringNode == null) {
                            System.out.println();
                        }
                        rootStringNode.rightNode = stringNode;
                    } else if (preCharecter != null && preCharecter == '(') {
                        rootStringNode.leftNode = stringNode;
                    } else {
                        rootStringNode = stringNode;
                    }
                    if (returnNode == null) {
                        returnNode = stringNode;
                    }
                    stringNode.parentNode = rootStringNode;
                    preStringNode = stringNode;
                    preCharecter = c;
                //进位
                }else if(c == '(') {
                    rootStringNode = preStringNode;
                    preCharecter = c;
                //退位
                }else if(c == ')'&& rootStringNode!=null){
    
                    if(rootStringNode.parentNode == null){
                        System.out.println(rootStringNode.parentNode);
                    }
    
                    rootStringNode = rootStringNode.parentNode;
                    preCharecter = c;
                }else if(c == ','){
                    preCharecter = c;
                }
                index++;
            }
            return returnNode;
        }
    }
    
    class StringNode{
    
        public StringNode parentNode;
    
        public  Character value;
    
        public StringNode leftNode;
    
        public StringNode rightNode;
    
    }

输出结果：

A  
  B   E  
C    
  D  
 F  G

思路是

1.左右节点边界值。

2.双向连接这样可以进行回溯。

3.注意parentNode 的下降和回撤过程。