algorithm - 将排序链表转换为平衡二叉树未正确返回？

Question

以下是我编写的用于将 linkedList 转换为 Balanced BinarySearch Tree 的关键方法。我得到 BST 但它不平衡。为什么会这样？

public static Node headNode;

public static IntTreeNode convertLinkedListToBST(Node node){
            int len = getCount(node);
            headNode = node;
            return convertLinkedListToBSThelper(node, 0, len-1);


    }
    //http://www.programcreek.com/2013/01/leetcode-convert-sorted-list-to-binary-search-tree-java/
    public static IntTreeNode convertLinkedListToBSThelper(Node node, int start, int end) {
        if (start>end)
            return null;
        int mid=start+end >>1 ;
        IntTreeNode left = convertLinkedListToBSThelper(node, start, mid-1);
        IntTreeNode root = new IntTreeNode(headNode.data);
        headNode=headNode.next;
        IntTreeNode right = convertLinkedListToBSThelper(node, mid+1, end);
        root.left=left;
        root.right=right;
        return root;
    }

private static int getCount(Node node){
    int count=0;
    Node current = node;
    while(current!=null){
        current=current.next;
        count++;
        }
    return count;
}

主要方法如下:

Node node = new Node(1);
node.next=new Node(2);
node.next.next=new Node(3);
node.next.next.next=new Node(4);
node.next.next.next.next=new Node(5);
node.next.next.next.next.next=new Node(6);
node.next.next.next.next.next.next=new Node(7);
node.next.next.next.next.next.next.next=new Node(8);

System.out.println("***********");
IntTreeNode result1 = convertLinkedListToBST(node);
System.out.println("preOrder");
printPreOrder(result1);
System.out.println("inOrder");
printInOrder(result1);
System.out.println("postOrder");
printPostOrder(result1);
System.out.println();
System.out.println(isValidBST(result1));
List<Integer> list = new ArrayList<>();
printLevelorder(result1, list);
System.out.println(list);

这是我得到的输出(为了便于阅读而格式化):

preOrder  4, 1, 2, 3, 5, 6, 7, 8, 
inOrder   1, 2, 3, 4, 5, 6, 7, 8, 
postOrder 1, 2, 3, 5, 6, 7, 8, 4, 
true
[4, 2, 6, 1, 3, 5, 7, 8]

Level order 和 preOrder 不匹配构建唯一树。这里有什么提示吗？

Answer 1

您的 convertLinkedListToBSThelper 和 getcount 方法运行良好。我在我的代码中使用了这两种方法。

import java.util.*;


class Solution{
static Node headNode;
    public static void main(String args[]){
    
    Node node = new Node(1);
    headNode=node;
    Node node1 = new Node(2);
    Node node2 = new Node(3);
    Node node3 = new Node(4);
    Node node4 = new Node(5);
    Node node5 = new Node(6);
    Node node6 = new Node(7);
    Node node7 = new Node(8);
    node.setnext(node1);
    node1.setnext(node2);
    node2.setnext(node3);
    node3.setnext(node4);
    node4.setnext(node5);
    node5.setnext(node6);
    node6.setnext(node7);
    node7.setnext(null);
    int len=getCount(node);
    Node result1=convertLinkedListToBSThelper(node, 0, len-1);

System.out.println("preOrder");
preorder(result1);
System.out.println();
System.out.println("inOrder");
inorder(result1);
System.out.println();
System.out.println("postOrder");
postorder(result1);
System.out.println("levelOrder");
levelorder(result1);
}

public static Node convertLinkedListToBSThelper(Node node, int start, int end) {
        if (start>end)
            return null;
        int mid=start+end >>1 ;
        Node left = convertLinkedListToBSThelper(node, start, mid-1);
        Node root = new Node(headNode.getdata());
       
        headNode=headNode.next;
        Node right = convertLinkedListToBSThelper(node, mid+1, end);
        root.setleft(left);
        root.setright(right);
        return root;
    }

private static int getCount(Node node){
    int count=0;
    Node current = node;
    while(current!=null){
        current=current.next;
        count++;
        }
    return count;
}

public static void preorder(Node temp){
  if(temp==null)
     return;
   System.out.print(temp.data+" ");
   preorder(temp.getleft());
   preorder(temp.getright());
}

public static void inorder(Node temp){
  if(temp==null)
     return;
   inorder(temp.getleft());
   System.out.print(temp.data+" ");
   inorder(temp.getright());
}

public static void postorder(Node temp){
	  if(temp==null)
	     return;
	   postorder(temp.getleft());
       postorder(temp.getright());
	   System.out.print(temp.data+" ");	
}

public static void levelorder(Node temp)
{
   Queue<Node> q=new LinkedList<Node>();
   q.add(temp);
   while(!q.isEmpty()){
	   Node a=q.remove();
	   System.out.print(a.getdata()+" ");
	   if(a.getleft()!=null)
	   q.add(a.getleft());
	   if(a.getright()!=null)
	   q.add(a.getright());
   }
   
}
    
} 
class Node{
    int data;
    Node next;
    Node left;
    Node right;
    public Node(int i) {
		this.data=i;
    	// TODO Auto-generated constructor stub
	}
	
    public  void  setnext(Node temp){
        this.next=temp;
    }
    public  Node getnext(){
        return this.next;
    }
    public  void  setleft(Node temp){
        this.left=temp;
    }
    public  Node getleft(){
        return this.left;
    }
    public  void  setright(Node temp){
        this.right=temp;
    }
    public  Node getright(){
        return this.right;
    }
    public int getdata(){
      return this.data;
    }

}

我认为你在某些遍历方法上犯了错误。请与我一起检查。如果您有问题，请粘贴整个代码。顺便说一句，我的代码给出了输出

preOrder
4 2 1 3 6 5 7 8 
inOrder
1 2 3 4 5 6 7 8 
postOrder
1 3 2 5 8 7 6 4 
levelOrder
4 2 6 1 3 5 7 8 

还有一件事总是存在具有给定以下组合的唯一二叉树(可能是平衡 BST 或 BST)

Inorder and Preorder.
Inorder and Postorder.
Inorder and Level-order.