109. Convert Sorted List to Binary Search Tree

原題

• 題目描述: 把一個升序連結清單建構成左右子樹深度相差不過1的平衡樹
• 思路:建構樹一般而言用遞歸生成
  1. 先定義兩個快慢指針,一路往前走,當快指針到達尾結點或者尾結點的前驅結點時循環結束.
  2. 建立樹節點,結點資料域為此時慢指針指向的結點的元素值,并由此遞歸其建構左子樹,而其左子樹的資料域均取自頭結點到慢指針這段(原連結清單的前半段)
  3. 其右子樹的資料域均取自慢結點後繼結點到空結點這段(原連結清單的後半段)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head==null){
            return null;
        }
        return buildBST(head,null);
    }
    public TreeNode buildBST(ListNode head,ListNode tail){
        ListNode fast=head;
        ListNode slow=head;
        if(head==tail){//當頭尾相遇時傳回空
            return null;
        }
        while(fast!=tail&&fast.next!=tail){//快指針指向尾結點和其前驅結點時結束
            fast=fast.next.next;
            slow=slow.next;
        }
        TreeNode treeNode=new TreeNode(slow.val);//根節點(值為慢指針的值,取自有序連結清單的中間值)
        treeNode.left=buildBST(head,slow);//連結清單前半段放左子樹
        treeNode.right=buildBST(slow.next,tail);//連結清單後半段放右子樹
        return treeNode;//傳回樹的根節點
    }
}