带括号的二叉树，而 != null 将不起作用

Question

我正在开发一个程序，该程序接受表示前缀格式二进制表达式（例如 (A(B(C)(D))(E(F)(G))) ）的字符串。我一直坚持算法的一部分，根据来自单独堆栈的括号将数据添加到节点（在根 A 之后，'('indicates a left node while ')' 后跟 '(' 表示正确。我的代码似乎运行足够好，直到我输入以下代码：

if (focus != null && val == '(') {
                    char nodeVal = tree.pop();
                    Node node = new Node(nodeVal);
                    focus = root;
                    while(focus != null) {
                        focus = focus.leftNode;
                    }
                    focus = node;

它通过了“if (focus != null)”，但是当它遇到 while 循环时，它要么 returns 一个错误，要么不添加新节点，要么创建一个无限循环 (基于我一直在尝试的一些变体。如果有帮助，该方法的完整代码如下：

public void constructTree(String input) {
            
            for(int i = input.length()-1; i>=0; i--) {
                if(input.charAt(i) == '(' || input.charAt(i) == ')') {
                    paren.push(input.charAt(i));
                }
                else {
                    tree.push(input.charAt(i));
                }
            }
            while(!paren.isEmpty()) {
                char val = paren.pop();
                Node focus = root;
                Node parent;
                
    
                if (val == ')' && root == null) {
                    throw new InvalidTreeSyntax("Your tree cannot be empty");
                }
                if (root == null) {
                    char nodeVal = tree.pop();
                    Node node = new Node(nodeVal);
                    
                    root = node;
                }
                                
                if (focus != null && val == '(') {
                        char nodeVal = tree.pop();
                        Node node = new Node(nodeVal);
                        focus = root;
                        while(focus != null) {
                            focus = focus.leftNode;
                        }
                        focus = node;
                        
                        
                    }
                else if (focus != null  && val == ')' && paren.peek()== '(' || paren.peek() == null) {
                    char nodeVal = tree.pop();
                    Node node = new Node(nodeVal);
                    paren.pop();
                    while(focus!= null) {
                        focus = focus.rightNode;
                    }
                    focus = node;
                    
                }

            }
        }

我敢肯定这是一个简单的错误，但是在吃饱了火鸡却又没有足够的睡眠之后，我脑残了，需要一些帮助！

Answer 1

这是一个递归的解决方案。

record Node(char value, Node left, Node right) {}

static Node constructTree(Deque<Integer> que) {
    if (que.peek() != '(')
        return null;
    que.pop();
    if (que.peek() == '(' || que.peek() == ')')
        throw new RuntimeException("node value expected");
    char nodeValue = (char)(int)que.pop();
    Node left = constructTree(que);
    Node right = constructTree(que);
    if (que.peek() != ')')
        throw new RuntimeException("')' expected");
    que.pop();
    return new Node(nodeValue, left, right);
}

static Node consturctTree(String s) {
    return constructTree(s.chars().boxed()
        .collect(Collectors.toCollection(ArrayDeque::new)));
}

public static void main(String[] args) throws IOException, ClassNotFoundException {
    String source = "(A(B(C)(D))(E(F)(G)))";
    Node root2 = consturctTree(source);
    System.out.println(root2);
}

输出：（已编辑）

Node[value=A,
    left=Node[value=B,
        left=Node[value=C, left=null, right=null],
        right=Node[value=D, left=null, right=null]],
    right=Node[value=E,
        left=Node[value=F, left=null, right=null],
        right=Node[value=G, left=null, right=null]]]

带括号的二叉树，而 != null 将不起作用

Parenthesized binary tree, while != null won't work

java

binary-tree

nodes