java - 将单链表排序到 BST

Question

我已经引用了很多帖子和答案，但仍然无法获得工作代码。下面是在 java 中将链表排序到 BST 的代码。包括链表的所有辅助函数。

我得到的输出不是预期的，即 root : 4 ， root.left 是 2 而 root.right 又是 4 。我想输出应该是 root : 4 ， root.left 是 2 和 root.right 是 6

class LNode {
    public int data;
    public LNode next;

    LNode(int newData) {
        this.data = newData;
    }
}

class Node {

    int data;
    Node left;
    Node right;
    public Node prev;

    Node(int d) {
        data = d;
        left = right = null;
    }
}

class LinkedList {
    LNode first;
    LNode head;
    LNode newNode;

    public LinkedList() {
        first = null;
    }

    public void insertAtBeginning(int x) {
        newNode = new LNode(x);
        if (first != null) {
            newNode.next = first;
            first = newNode;
            head = first;
        } else {
            first = newNode;
            head = first;
        }
    }

    public void printList()

    {
        head = first;
        while (first != null) {
            System.out.print(first.data + " --> ");
            first = first.next;
        }
        System.out.println("null");
        first = head;

    }
}

public class LLtoBST {
    public static Node root;
    //public static LNode first;

    public static Node sortedListToBST(LNode first, int end) {

        return sortedListToBST(first, 0, end);
    }

    public static Node sortedListToBST(LNode first, int start, int end) {

        if (start > end)
            return null;
        if (first != null) {
            int mid = start + (end - start) / 2;

            Node lnode = sortedListToBST(first, start, mid - 1);

            root = new Node(first.data);

            first = first.next;
            Node rnode = sortedListToBST(first, mid + 1, end);

            root.left = lnode;
            root.right = rnode;

        }
        return root;

    }

    public static void main(String... args) {
        LinkedList list = new LinkedList();
        int n = 0;
        list.insertAtBeginning(7);
        list.insertAtBeginning(6);
        list.insertAtBeginning(5);
        list.insertAtBeginning(4);
        list.insertAtBeginning(3);
        list.insertAtBeginning(2);
        list.insertAtBeginning(1);
        list.printList();

        first = list.head;

        while (first != null) {
            n++;
            first = first.next;
        }

        first = list.head;

        Node curr = sortedListToBST(first, n);
        System.out.println(curr.data);
        System.out.println(curr.left.data);
        System.out.println(curr.right.data);

    } 

}

Output :
1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> null
4
2
4

如有任何帮助，我们将不胜感激。

Answer 1

请在函数 sortedListToBST(LNode first, int start, int end) 中进行以下更改

请注意，下面的代码将 2 打印为 4 的左 child ，并将 6 打印为 4 的右 child 。另外，我已经测试了以 2 和 6 作为根的代码。它打印 1 作为 2 的左 child ，3 作为 2 的右 child 。另外，5 作为 6 的左 child ，7 作为 6 的右 child 。

另请注意，您需要更改测试客户端，以便它处理左 child 和/或右 child 为空时的用例。我希望下面的代码对您有所帮助。

下面的算法基于树的中序遍历原理。

1. 遍历左子树。
2. 访问根。

3. 遍历右子树。

   public static Node sortedListToBST(LNode first, int start, int end) {
   
   if (start > end)
       return null;
   
   int mid = (start + end) / 2;
   Node leftNode = sortedListToBST(first, start, mid - 1);
   Node root = new Node(first.data);
   root.left = leftNode;
   if (first.next != null) {
       first.data = first.next.data;
       first.next = first.next.next;
   }
   
   root.right = sortedListToBST(first, mid + 1, end);
   return root;
   
   }