java - 将二叉搜索树转换为双向链表 - 不起作用

Question

我粘贴的解决方案来自 this Geek URL

它是用 C 编写的，所以我尝试将其转换为 JAVA，如下所示 -(如果我错了，请纠正我，我不是 c/c++ 人)

程序

   // A simple recursive function to convert a given Binary tree to Doubly
   // Linked List
   // root --> Root of Binary Tree
   // head --> Pointer to head node of created doubly linked list
   public void BinaryTree2DoubleLinkedList(BTNodes root, BTNodes head)
   {
           if(root == null)
               return;

           // Initialize previously visited node as NULL. This is
           // declared outside the recursive function so that the same value 
           // is accessible in all recursive calls   

            prev = null;

            // Recursively convert left subtree
            BinaryTree2DoubleLinkedList(root.getLeft(), head);

            //set head of LL if not set
            if(orgHead == null)
                orgHead = root;

            // Now convert this node
            if (prev == null)
                head = root;
            else
            {
                root.setLeft(prev);
                prev.setRight(root);
            }
            prev = root;

            // Finally convert right subtree
            BinaryTree2DoubleLinkedList(root.getRight(), head);
    }

考虑中的树

            10
          /   \
         5    15
        / \  /   \
       2  7 12   18
      /
     1
    /
   0

问题

这个程序返回输出:

0 1 2 5 7 10 15 18

如您所见，代码中缺少 12。我尝试空运行了很多次，但仍然无法找出真正的问题......我尝试搜索不同的解决方案，但大多数解决方案都在 part-converted-LL 中遍历，这增加了时间复杂度。

Answer 1

原C代码函数原型(prototype)如下:

void BinaryTree2DoubleLinkedList(node *root, node **head)

**head 表示双指针，head 值可以在函数内使用*head 改变。在java中你不能修改函数参数因为它们总是被复制，但是你可以修改数组元素。所以请尝试以下代码:

BTNode prev;

void BinaryTree2DoubleLinkedList(BTNodes root, BTNodes[] head)
{
    // Base case
    if (root == null) return;

    // Initialize previously visited node as NULL. This is
    // static so that the same value is accessible in all recursive
    // calls

    // Recursively convert left subtree
    BinaryTree2DoubleLinkedList(roor.getLeft(), head);

    // Now convert this node
    if (prev == null)
        head[0] = root;
    else
    {
        root.setLeft(prev);
        prev.setRight(root);
    }
    prev = root;

    // Finally convert right subtree
    BinaryTree2DoubleLinkedList(root.getRight(), head);
}

初始调用应如下所示:

BTNodes[] head = new BTNodes[1];
BinaryTree2DoubleLinkedList(root, head);
// result is in head[0]

为了更好地避免对 head 元素进行丑陋的分配，可以创建如下附加功能:

BTNodes BinaryTree2DoubleLinkedList(BTNodes root) {
    BTNodes[] head = new BTNodes[1];
    BinaryTree2DoubleLinkedList(root, head);
    return head[0];
}