LeetCode OJ 109. Convert Sorted List to Binary Search Tree

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

涉及到二叉树的问题用递归的方法很容易理解。这个问题要求把一个升序排序的链表转换为一颗height balanced BST。转换的方式就是把链表的中间值作为树的根节点，中间值的左半部分转换为二叉树的左子树，中间值的右半部分转换为二叉树的右子树。

递归解决问题的步骤如下：

1. 如果链表的长度为0，返回null；

2. 如果链表长度为1，创建新的二叉树节点node，node.left=null，node.right=null，node.val=head.val。

3. 否则的话找到链表的中间节点，即第mid = length%2==0?length/2:length/2+1个节点为根节点node。此时链表被分成两个部分，前半部分的长度为mid-1，后半部分的长度为length-mid，递归求这两部分的结果，并把他们分别赋值给根节点的左子树和右子树。代码如下：

 public class Solution {

     public TreeNode sortedListToBST(ListNode head) {

         ListNode pointer = head;

         int length = 0;

         while(pointer!=null){

             pointer = pointer.next;

             length++;

         }

         return listToBST(head, length);

     }

     public TreeNode listToBST(ListNode head,int length){

         if(length==0) return null;

         if(length==1){

             TreeNode node = new TreeNode(head.val);

             node.left = null;

             node.right = null;

             return node;

         }

         if(length==2){

             TreeNode node = new TreeNode(head.val);

             node.left = null;

             node.right = listToBST(head.next, 1);

             return node;

         }

         int mid = length%2==0?length/2:length/2+1;

         ListNode pointer = head;

         ListNode righthead = null;

         int i = 1;

         while(pointer.next!=null && i<mid-1){

             pointer = pointer.next;

             i++;

         }

         TreeNode node = new TreeNode(pointer.next.val);

         righthead = pointer.next.next;

         pointer.next = null;

         node.left = listToBST(head, mid-1);

         node.right = listToBST(righthead, length-mid);

         return node;

     }

 }