LeetCode 109. Convert Sorted List to Binary Search Tree

[Woodyiiiiiii]

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

---

这道题要求把有序链表转化为高度优先的二叉搜索树。
受108. Convert Sorted Array to Binary Search Tree的启发，我们可以遍历链表，将节点的值域依次存入数组中，得到一个有序数组，然后利用二分法和先序创建二叉树的方法得到目标的高度优先的BST。

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null; 
        int[] nodes = list2Array(head);
        TreeNode root = new TreeNode();
        root = create(root, nodes, 0, nodes.length - 1);
        return root;
    }
    public int[] list2Array(ListNode head) {
        if (head == null) return new int[0];
        ListNode node = head;
        int len = 0;
        while (node != null) {
            ++len;
            node = node.next;
        }
        node = head;
        int i = 0;
        int[] nodes = new int[len];
        while (node != null) {
            nodes[i++] = node.val;
            node = node.next;
        }
        return nodes;
    }
    public TreeNode create(TreeNode node, int[] nodes, int left, int right) {
        if (left > right) return null;
        int mid = left + (right - left) / 2;
        node = new TreeNode(nodes[mid]);
        node.left = create(node.left, nodes, left, mid - 1);
        node.right = create(node.right, nodes, mid + 1, right);
        return node;
    }
}

当然我们可以在原链表基础上操作，不需要转化为数组。思路就是先利用快慢指针找到当前链表的中间节点的前一个节点，然后同样利用先序遍历创建二叉树的思路，为了方便断开链表，首先创建右子节点，从中间断开链表后再创建左子节点，递归即可。重点是如何规划代码逻辑。

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        ListNode slow = head, fast = head;
        // 如果我们是要找到中间节点，那么没有此片段
        if (fast != null && fast.next != null)
            fast = fast.next.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode node = new TreeNode(slow.next.val);
        node.right = sortedListToBST(slow.next.next);
        slow.next = null;
        node.left = sortedListToBST(head);
        return node;
    }
}

---

参考资料：

• https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
• https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35567/Java-fast-slow-pointer-recursive-solution.