1 /**  2  * Definition for singly-linked list.  3  * public class ListNode {  4  *     int val;  5  *     ListNode next;  6  *     ListNode(int x) { val = x; next = null; }  7  * }  8  */  9 /** 10  * Definition for binary tree 11  * public class TreeNode { 12  *     int val; 13  *     TreeNode left; 14  *     TreeNode right; 15  *     TreeNode(int x) { val = x; } 16  * } 17  */ 18 public class Solution { 19     public TreeNode root ; 20     public int nums[]; 21      22     public TreeNode sortedListToBST(ListNode head) {        23         ListNode temp = head; 24         int length = 0; 25         while(temp != null){ 26             length ++; 27             temp = temp.next;                     28         } 29         nums = new int[length]; 30         temp = head; 31         for(int i = 0; i < nums.length; i++){ 32             nums[i] = temp.val; 33             temp = temp.next; 34         } 35         return sortedArrayToBST(nums); 36     } 37  38     public TreeNode sortedArrayToBST(int[] num) { 39         if(num.length == 0) 40             return root; 41         if(1 == num.length){ 42             return new TreeNode(num[0]); 43         } 44         int middle = num.length / 2; 45         root = new TreeNode(num[middle]); 46          47         createBST(num, 0, middle - 1); 48         createBST(num, middle + 1, num.length - 1); 49         return root; 50     } 51      52     /** 53      * 根据num数组，创建一棵二叉查找树 54      * @param num 55      * @param start 56      * @param end 57      */ 58     private void createBST(int num[], int start, int end){ 59         int middle = 0; 60         if(start <= end && start >= 0 && end <num.length){ 61             middle = (start + end) / 2; 62              63             insertNode(root, num[middle]); 64              65             createBST(num, start, middle - 1); 66             createBST(num, middle + 1, end); 67         } 68     } 69      70     /** 71      * 向root所指的BST二叉查找树中插入value 72      * @param root 73      * @param value 74      */ 75     private void insertNode(TreeNode root, int value){         76         if(value > root.val){                    //比根节点大,在右子树插入 77             if(root.right == null){ 78                 root.right = new TreeNode(value); 79             }else{ 80                 root = root.right; 81                 insertNode(root, value); 82             } 83         } 84         else{ 85             if(root.left == null){ 86                 root.left = new TreeNode(value); 87             }else{ 88                 root = root.left; 89                 insertNode(root, value);            //比根节点小的插入左子树 90             } 91         } 92     } 93      94     /** 95      * 先序遍历 96      * @param root 97      */ 98     public void preTravel(TreeNode root){ 99         if(root != null){100 //            System.out.print(root.val + " ");101             preTravel(root.left);102             preTravel(root.right);103         }104     }105 }