java - 在JAVA中将二叉搜索树转换为链表

Question

 public static BiNode linklist(BiNode root)
 {
    BiNode head = null, tail=null;
    convertBST(head, tail, root);
    return head;
 }



 public static void convertBST(BiNode head, BiNode tail, BiNode root)
 {
    BiNode leftTail = null, rightHead = null;
    if(root==null){
        head = null;
        tail = null;
        return;
    }
    System.out.println("root = "+root.key);
    convertBST(head, leftTail, root.node1);
    convertBST(rightHead, tail, root.node2);
    if(leftTail != null)
    {
        System.out.println("leftTail = "+leftTail.key);
        leftTail.node2 = root;
        root.node1 = leftTail;
    }else{
        head = root;
        System.out.println("head = "+ head.key+", root = "+root.key);
    }

       if(rightHead != null)
       {
        rightHead.node1 = root;
        root.node2 = rightHead;
       }else{
        tail = root;
        System.out.println("tail = "+ tail.key+", root = "+root.key);
       }
  }

以上是我的 java 代码，用于将 BST 转换为双链表。

但是不知道为什么head总是变，应该是指向链表的head，不会变。

我很高兴伟大的头脑能帮我调试这段代码!谢谢!!!

Answer 1

关于代码错误原因的基本关键是这一行: head = root; 和 tail = root; 在方法 public static void convertBST (BiNode head, BiNode tail, BiNode root)

您假设当您将参数设置为新节点时，它会向上传播调用堆栈(通过引用调用)。 Java 不这样做。当您执行 head = root; 时，您只是更改了 head 的本地值，而不是调用方法中的值。

因此在方法 public static BiNode linklist(BiNode root){ 中，head 将始终为 null 并且该方法将始终返回 空。