获取二叉树的点括号表示

问：

我在获取二叉树的点括号表示时遇到问题。

• 没有节点的树的点括号表示是字符串 “.”

• 具有根节点 r 的二叉树的点括号表示由一个开放的 括号（后跟 R.Left 的点括号表示，后跟 R.Right 的点括号表示，后跟右括号）

示例：像这样的树： 树：（（（）（）（）（））(((((）(((((）））（（） 应该输出 bracketSequence（） = （（（..）((..)(..)))((.(((..)((((.(..)).).)(.(..))))(..)))(..)))

检查我的 bracketSequenceNEW（） 了解我尝试过的内容。

检查我的 bracketSequenceNEW（） 了解我尝试过的内容。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;

public class BinaryTree<Node extends BinaryTree.BTNode<Node>> {

    public static class BTNode<Node extends BTNode<Node>> {
        public Node left;
        public Node right;
        public Node parent;
    }

    /**
     * An extension of BTNode that you can actually instantiate.
     */
    protected static class EndNode extends BTNode<EndNode> {
            public EndNode() {
                this.parent = this.left = this.right = null;
            }
    }

    /**
     * Used to make a mini-factory
     */
    protected Node sampleNode;

    /**
     * The root of this tree
     */
    protected Node r;

    /**
     * This tree's "null" node
     */
    protected Node nil;

    /**
     * Create a new instance of this class
     * @param sampleNode - a sample of a node that can be used
     * to create a new node in newNode()
     * @param nil - a node that will be used in place of null
     */
    public BinaryTree(Node sampleNode, Node nil) {
        this.sampleNode = sampleNode;
        this.nil = nil;
        r = nil;
    }

    /**
     * Create a new instance of this class
     * @param sampleNode - a sample of a node that can be used
     * to create a new node in newNode()
     */
    public BinaryTree(Node sampleNode) {
        this.sampleNode = sampleNode;
    }

    /**
     * Allocate a new node for use in this tree
     * @return newly created node
     */
    @SuppressWarnings({"unchecked"})
    protected Node newNode() {
        try {
            Node u = (Node)sampleNode.getClass().getDeclaredConstructor().newInstance();
            u.parent = u.left = u.right = nil;
            return u;
        } catch (Exception e) {
            return null;
        }
    }

    /**
     * Construct a random binary tree
     * @return an n-node BinaryTree that has the shape of a random
     * binary search tree.
     */
    public static BinaryTree<EndNode> randomBST(int n) {
        Random rand = new Random();
        EndNode sample = new EndNode();
        BinaryTree<EndNode> t = new BinaryTree<EndNode>(sample);
        t.r = randomBSTHelper(n, rand);
        return t;
    }

    protected static EndNode randomBSTHelper(int n, Random rand) {
        if (n == 0) {
            return null;
        }
        EndNode r = new EndNode();
        int ml = rand.nextInt(n);
        int mr = n - ml - 1;
        if (ml > 0) {
            r.left = randomBSTHelper(ml, rand);
            r.left.parent = r;
        }
        if (mr > 0) {
            r.right = randomBSTHelper(mr, rand);
            r.right.parent = r;
        }
        return r;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        toStringHelper(sb, r);
        return sb.toString();
    }

    protected void toStringHelper(StringBuilder sb, Node u) {
        if (u == null) {
            return;
        }
        sb.append('(');
        toStringHelper(sb, u.left);
        toStringHelper(sb, u.right);
        sb.append(')');
    }

    /**
     * Tree empty or not
     * @return true if empty, false otherwise
     */
    public boolean isEmpty() {
        return r == nil;
    }

    /**
     * Make this tree into the empty tree
     */
    public void clear() {
        r = nil;
    }

    /**
     * Compute the depth (distance to the root) of u
     * @param u
     * @return the distanct between u and the root, r
     */
    public int depth(Node u) {
        int d = 0;
        while (u != r) {
            u = u.parent;
            d++;
        }
        return d;
    }

    /**
     * Demonstration of a recursive traversal
     * @param u
     */
    public void traverse(Node u) {
        if (u == nil) return;
        traverse(u.left);
        traverse(u.right);
    }

    /**
     * Demonstration of a non-recursive traversal
     */
    public void traverse2() {
        Node u = r, prev = nil, next;
        while (u != nil) {
            if (prev == u.parent) {
                if (u.left != nil) {
                    next = u.left;
                } else if (u.right != nil) {
                    next = u.right;
                }   else {
                    next = u.parent;
                }
            } else if (prev == u.left) {
                if (u.right != nil) {
                    next = u.right;
                } else {
                    next = u.parent;
                }
            } else {
                next = u.parent;
            }
            prev = u;
            u = next;
        }
    }

    /**
     * Demonstration of a breadth-first traversal
     */
    public void bfTraverse() {
        Queue<Node> q = new LinkedList<Node>();
        if (r != nil) q.add(r);
        while (!q.isEmpty()) {
            Node u = q.remove();
            if (u.left != nil) q.add(u.left);
            if (u.right != nil) q.add(u.right);
        }
    }

    /**
     * Compute the size (number of nodes) of this tree
     * @warning uses recursion so could cause a stack overflow
     * @return the number of nodes in this tree
     */
    public int size() {
        return size(r);
    }

    /**
     * @return the size of the subtree rooted at u
     */
    protected int size(Node u) {
        if (u == nil) return 0;
        return 1 + size(u.left) + size(u.right);
    }

    /**
     * Compute the maximum depth of any node in this tree
     * @return the maximum depth of any node in this tree
     */
    public int height() {
        return height(r);
    }

    /**
     * @return the height of the subtree rooted at u
     */
    protected int height(Node u) {
        if (u == nil) return -1;
        return 1 + Math.max(height(u.left), height(u.right));
    }

    public int leafAndOnlyLeaf() {
        // TODO: Your code goes here, must avoid recursion
        if (r == nil) return 0;
        
        Queue<Node> queue = new LinkedList<>();
        queue.add(r);
        int leafCount = 0;
        
        while (!queue.isEmpty()) {
            Node u = queue.remove();
            
            // Check if the node is a leaf
            if (u.left == nil && u.right == nil) {
                leafCount++;
            }
            
            // Add children to the queue if they exist
            if (u.left != nil) queue.add(u.left);
            if (u.right != nil) queue.add(u.right);
        }
        
        return leafCount;
    }
    protected int leafAndOnlyLeafHelper(Node u) {
        if(u == nil)return 0;
        if(u.left == nil && u.right == nil)return 1;
        return leafAndOnlyLeafHelper(u.left)+ leafAndOnlyLeafHelper(u.right);
    }

    
    public int dawnOfSpring() {
        if (r == nil) return -1;
        
        Queue<Node> queue = new LinkedList<>();
        queue.add(r);
        int depth = 0;
        
        while (!queue.isEmpty()) {
            int nodeCount = queue.size();
            
            while (nodeCount > 0) {
                Node u = queue.remove();
                
                // Check if the node is a leaf
                if (u.left == nil && u.right == nil) {
                    return depth;
                }
                
                // Add children to the queue if they exist
                if (u.left != nil) queue.add(u.left);
                if (u.right != nil) queue.add(u.right);
                
                nodeCount--;
            }
            depth++;
        }
        
        return -1; // Should never reach here if the tree has at least one node
    }
    

    

    protected int dawnOfSpringHelper(Node u, int d) {
        if(u.left == nil && u.right == nil)
            return d;
        else if(u.left == nil)
            return dawnOfSpringHelper(u.right, d+1);
        else if(u.right == nil)
            return dawnOfSpringHelper(u.left, d+1);
        else
            return Math.min(dawnOfSpringHelper(u.left, d+1), dawnOfSpringHelper(u.right, d+1));
    }


    
    
    public int monkeyLand() {
        if (r == nil) return 0;
    
        Queue<Node> currentLevel = new LinkedList<>();
        currentLevel.add(r);
    
        int maxNodes = 0; // Maximum number of nodes at any level
        int maxDepth = 0; // Depth which has the maximum number of nodes
        int currentDepth = 0; // Current depth in the tree
    
        while (!currentLevel.isEmpty()) {
            int levelCount = currentLevel.size(); // Number of nodes at the current level
            if (levelCount > maxNodes) {
                maxNodes = levelCount;
                maxDepth = currentDepth;
            }
    
            // Prepare for the next level
            Queue<Node> nextLevel = new LinkedList<>();
            while (!currentLevel.isEmpty()) {
                Node u = currentLevel.remove();
                if (u.left != nil) nextLevel.add(u.left);
                if (u.right != nil) nextLevel.add(u.right);
            }
    
            // Move to the next level
            currentLevel = nextLevel;
            currentDepth++;
        }
    
        return maxDepth;
    }
    
    
    
    

    protected int monkeyLandHelper(Node u, int d, int D) {
        if(u == nil) return 0;
        if(d == D)return 1;
        return monkeyLandHelper(u.left, d+1, D) + monkeyLandHelper(u.right, d+1, D);
    }



    // use sb.append(), must avoid recursion
    public String bracketSequenceNEW() {
        if (r == nil) return "."; // Handle the empty tree case
    
        StringBuilder sb = new StringBuilder();
        Stack<Node> stack = new Stack<>();
        Node current = r;
        Node prev = nil;
    
        while (!stack.isEmpty() || current != nil) {
            if (current != nil) {
                stack.push(current);
                sb.append("("); // Start a new node
                if (current.left != nil) {
                    current = current.left; // Move to left child
                } else {
                    sb.append("."); // Left child is missing
                    if (current.right != nil) {
                        current = current.right; // Move to right child
                    } else {
                        sb.append("."); // Right child is also missing
                        current = nil; // No children, move up the tree
                    }
                }
            } else {
                Node node = stack.peek(); // Look at the top node without popping it
                if (node.right != nil && node.right != prev) {
                    current = node.right; // Move to right child
                } else {
                    if (node.right == nil && prev != node.left) {
                        sb.append("."); // Right child is missing and we didn't come from left child
                    }
                    stack.pop(); // Done with this node
                    sb.append(")"); // End the current node
                    prev = node; // Keep track of the last node we've finished
                }
            }
        }
    
        return sb.toString();
    }
    
    
    
    
    
    
    
    
    public String bracketSequence() {
        StringBuilder sb = new StringBuilder();
        bracketSequenceHelper(r, sb);
        return sb.toString();
    }
    
    
    
    
    

    

    protected void bracketSequenceHelper(Node u, StringBuilder sb){
        if (u == nil) {
            sb.append('.');
            return;
        }
        sb.append('(');
        bracketSequenceHelper(u.left, sb);
        bracketSequenceHelper(u.right, sb);
        sb.append(')');
    }
    
}

测试时 我得到这个输出

树：（（（））（（（))))))）（

大小（） = 20

leafAndOnlyLeaf（） = 9

dawnOfSpring（） = 2

monkeyLand（） = 4

括号序列（） = （（.（..））((((..)((..)((..).)))((..)(((..)((..)(..))).)))(..)))

括号序列 NEW） = （（.（..））((((...)((...)((...))))((...)(((...)((...)(...))))))(...)))

请注意，bracketSequence NEW 和 bracketSequence（） 应该具有相同的输出。