java - 二叉树和 NullPointerException

Question

此方法采用整数树并构造以下字符串:

(根部的数据，左子树的String，右子树的String)

例如，如果变量树存储对以下树的引用:

          +---+
          | 2 |
          +---+
         /     \
     +---+     +---+
     | 8 |     | 1 |
     +---+     +---+
    /         /     \
+---+     +---+     +---+
| 0 |     | 7 |     | 6 |
+---+     +---+     +---+
         /               \
     +---+               +---+
     | 4 |               | 9 |
     +---+               +---+

它应该返回一个字符串:

"(2, (8, 0, empty), (1, (7, 4, empty), (6, empty, 9)))"

对于空树，该方法应返回“empty”。对于叶节点，它应该以字符串形式返回节点中的数据。对于分支节点，它应该返回一个带括号的字符串，该字符串包含三个以逗号分隔的元素:

使用我的方法，它有时会起作用，但有时会生成 NullPointerException。谁能指出发生这种情况的地点和原因？

这是我的:

 private IntTreeNode overallRoot; // first node; linked to other nodes

 // post: returns the string of all data in leaves. For a branch node, return a parenthesized String
 //       w/ three elementsseparated by commas. return empty for empty tree
 public String toString2() {
     if (overallRoot == null) { // If empty tree
         return "empty";
     } else {
         return toString2(overallRoot);
     }
 }

 // helper for toString
 private String toString2(IntTreeNode root) {
     String value = "";
     if (root.left != null && root.right != null) { // If both branches exist
         value += "(" + root.data + ", " + toString2(root.left)+ ", " + toString2(root.right) + ")";  
     } else if (root.left != null && root.right == null) { // if right branch is empty
         value += "(" + root.data + ", " + toString2(root.left) + ", empty)";
     } else if (root.left == null && root.right != null) { // if left branch is empty
         value += "(" + root.data + ", empty, " + toString2(root.left) + ")";
     } else { // If at a leaf
         return "" + root.data;
     }
     return value;
 }

这是节点类:

public class IntTreeNode {
     public int data;
     public IntTreeNode left;
     public IntTreeNode right;

     // constructs a leaf node with given data
     public IntTreeNode(int data) {
         this(data, null, null);
     }

     // constructs a branch node with given data, left subtree,
     // right subtree
     public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) {
         this.data = data;
         this.left = left;
         this.right = right;
     }
}

Answer 1

错误在这里:

else if (root.left == null && root.right != null) { // if left branch is empty
         value += "(" + root.data + ", empty, " + toString2(root.left) + ")";
}

应该是……

else if (root.left == null && root.right != null) { // if left branch is empty
         value += "(" + root.data + ", empty, " + toString2(root.right) + ")";
}

...，将 root.right 而不是 root.left 传递给 toString2。