文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡書

1. 問題描述

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

2. 求解

這個(gè)題主要是根據(jù)一個(gè)有序鏈表構(gòu)造二叉查找樹（樹的左結(jié)點(diǎn)小于根節(jié)點(diǎn)，根節(jié)點(diǎn)小于右結(jié)點(diǎn)，子樹具有同樣的性質(zhì)）。與有序數(shù)組最大的不同在于有序鏈表只能從前往后遍歷，不能像有序數(shù)組一樣訪問任意位置的元素。因此構(gòu)造時(shí)需要按順序構(gòu)造，其實(shí)有序鏈表是二叉查找樹的中序遍歷。因此需要按照中序遍歷的順序進(jìn)行構(gòu)建，先構(gòu)建左子樹，再構(gòu)造根節(jié)點(diǎn)，最后構(gòu)造右子樹。由于是鏈表，每次構(gòu)造之后頭結(jié)點(diǎn)應(yīng)該進(jìn)行移動(dòng)，Java中用了一個(gè)靜態(tài)變量來保存根節(jié)點(diǎn)的位置。構(gòu)造方法主要是遞歸，每次構(gòu)建子樹時(shí)都需要將數(shù)組分成左右兩半，左邊的構(gòu)建左子樹，右邊的構(gòu)建右子樹，中間元素構(gòu)造根節(jié)點(diǎn)。

/**
 * 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; }
 * }
 */
public class Solution {
    static ListNode h;
    
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) {
            return null;
        }
        int length = 0;
        h = head;
        //得到鏈表長度
        while(head != null) {
            length++;
            head = head.next;
        }
        return buildBinarySearchTree(h, 0, length - 1);
    }
    
    public TreeNode buildBinarySearchTree(ListNode head, int start, int end) {
        if(start > end) {
            return null;
        }
        int mid = (start + end) / 2;
        //先構(gòu)建左子樹
        TreeNode left = buildBinarySearchTree(h, start, mid - 1);
        //再構(gòu)造根節(jié)點(diǎn)
        TreeNode root = new TreeNode(h.val);
        h = h.next;
        //最后構(gòu)造右子樹
        TreeNode right = buildBinarySearchTree(h, mid + 1, end);
        root.left = left;
        root.right = right;
        return root;
    }
}