leetcode: 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.

原问题链接：https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

 

问题分析

　　这个问题和前面的问题有点不一样，它的输入不是一个array，而是一个链表。那么，这个时候如果还是按照前面一个个遍历过去找位置然后设置节点的话，效率会很低。因此需要做一些调整。

 

方法一：

　　我们比较基于链表和基于数组的实现，前面基于数组的实现是需要根据当前节点所在的位置来定义根节点以及相对的左右子树。而链表的输入问题根源在于如果要找到一个元素所在的位置以及对应的元素值效率太低了。只要有办法找到这个就可以很快。

　　那么，我们可以用一个Map<Integer, ListNode>来保存在链表里每个元素的位置和它所对应的元素。然后再利用和前面基于数组同样的思路来递归构造平衡二叉搜索树。

　　详细的代码实现如下：

 

/**
 * 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 {
    private Map<Integer, ListNode> map = new HashMap<>();
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        int count = 0;
        ListNode node = head;
        while(node != null) {
            map.put(count, node);
            count++;
            node = node.next;
        }
        return sortedListToBST(map, 0, count - 1);
    }
    
    private TreeNode sortedListToBST(Map<Integer, ListNode> map, int l, int r) {
        if(l > r) return null;
        int mid = l + (r - l) / 2;
        TreeNode node = new TreeNode(map.get(mid).val);
        node.left = sortedListToBST(map, l, mid - 1);
        node.right = sortedListToBST(map, mid + 1, r);
        return node;
    }
}

　　这里的实现用Map保存了元素位置和元素值之间的映射，提升了查找元素的效率。但是整体的效率仍然一般，因为这里有一个从int到Integer元素的boxing和unboxing转换。

　　那么，除了上述的方法，还有没有其他的方法呢？

 

方法二

　　上面的那个办法也算是一个不错的思路了。不过这里还有一个办法更加巧妙。因为对于一个排序后的链表来说，它就相当于是对二叉树的中序遍历得到的结果。如果我们模拟一个二叉树中序遍历里递归调用回溯的过程，就可以一边遍历二叉树一边把对应的二叉树给建立起来。

　　比如说这里链表的第一个节点，它正好就对应二叉树的最左下角的元素。而它的下一个元素呢，正好就对应着前面二叉树递归调用里要回溯到的那个节点。于是我们可以有如下的代码实现：

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private ListNode cur;
    public TreeNode sortedListToBST(ListNode head) {
        cur = head;
        return generate(count(head));
    }
    
    private TreeNode generate(int n) {
        if(n == 0) return null;
        TreeNode node = new TreeNode(0);
        node.left = generate(n / 2);
        node.val = cur.val;
        cur = cur.next;
        node.right = generate(n - n / 2 - 1);
        return node;
    }
    
    private int count(ListNode node) {
        int count = 0;
        while(node != null) {
            count++;
            node = node.next;
        }
        return count;
    }
}

　　这种方法比较巧妙的糅合了二叉树中序遍历以及链表递进的关系，值得仔细揣摩。