converting sorted linked list to balanced binaryTr

问题:

Here are key methods I wrote for converting linkedList to Balanced BinarySearch Tree. I get BST but it is not balanced. why is it so?

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;
}

Here is main method:

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);

Here is the output I get (formatted for readability):

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 and preOrder does not match to build a unique tree. Any tips here ?

回答1:

Your convertLinkedListToBSThelper & getcount method work well.I have used your both method in my code.

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;
    }

}

I think you are doing mistake in some traversal method. Please check it out with mine.Still if you have problem just paste whole code. btw my code gives output

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 

One more thing there is always unique binary tree(may be balance BST or BST) with given following combination

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