二叉树抛出堆栈溢出异常，而无序遍历

Question

我正在学习数据结构，遇到了一个我无法解决的pbm。有人可以在这里帮忙吗？

我创建了一个TreeNode类。在同一个包中，我创建了另一个类。 这个类有两个方法。一种inorder遍历，还有另一种方法（从现有方法制作新的二叉树）。我称inorder遍历工作正常。但是如果我在另一个方法之后调用inorder遍历方法，我就会得到异常。

另一种方法创建一个新的二叉树，但它独立于遍历方法inorder

public class TreeNode {
     public int val;
     public TreeNode left;
     public TreeNode right;
     TreeNode(int x) { val = x; }
}
In the same package I created another class.
package BST;
public class Check {
    TreeNode curr;
    TreeNode prev;
public void orderTraversal( TreeNode curr1) {
        if(curr1 == null)
            return;
        orderTraversal(curr1.left);
        if(curr == null ) {
            curr = curr1;
            prev = curr1;
        }
        else {
            prev.right = curr1;
            prev = curr1;
        }
        orderTraversal(curr1.right);
    }
    public static void main(String[] args) {
            // TODO Auto-gene`enter code here`rated method stub
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.right = new TreeNode(15);
        Check check = new Check();  
        check.inOrder1(root);
        check.orderTraversal(root);
        check.inOrder1(root);
    }
    public  void inOrder1(TreeNode root) {
        if(root !=  null) {
            inOrder1(root.left); 
            System.out.printf("%d ",root.val);
            inOrder1(root.right);
        }
    }
}
When running the program , I am getting an exception in the method in the second call of inOrder1 . 
at sun.nio.cs.UTF_8.updatePositions(Unknown Source)
    at sun.nio.cs.UTF_8.access$200(Unknown Source)
    at sun.nio.cs.UTF_8$Encoder.encodeArrayLoop(Unknown Source)
    at sun.nio.cs.UTF_8$Encoder.encodeLoop(Unknown Source)
    at java.nio.charset.CharsetEncoder.encode(Unknown Source)
    at sun.nio.cs.StreamEncoder.implWrite(Unknown Source)
    at sun.nio.cs.StreamEncoder.write(Unknown Source)
    at java.io.OutputStreamWriter.write(Unknown Source)
    at java.io.BufferedWriter.flushBuffer(Unknown Source)
    at java.io.PrintStream.write(Unknown Source)
    at java.io.PrintStream.print(Unknown Source)
    at java.io.PrintStream.append(Unknown Source)

我知道 java 按值传递工作。第二种方法是仅引用实例变量。如果我check.orderTraversal(root)注释掉对InOrder1的第二次调用工作正常。我不知道为什么会这样？谁能帮忙？

谢谢！

Answer 1

在你的方法orderTraversal你正在修改你的树在行

prev.right = curr1;

那是你的错误。我真的不知道你打算在那里做什么，但你不应该在树遍历中修改你的树。

你说

第二种方法是仅引用实例变量

但是当你执行prev = curr1时，你的实例变量prev指向树中的节点。然后，当您执行prev.right = curr1时，您可以修改prev指向的节点。

因为修改树，所以要创建循环引用。节点 3 将节点 9 作为他的左子级，但节点 9 再次将 3（他自己的父级）作为他的左子级。这不再是一棵树，这就是为什么您第二次调用inOrder1时有无限数量的调用，以StackOverflowError结尾。

顺便说一下，这可以通过使用调试器轻松看到，我建议您查看此页面。