Convert Sorted List to Binary Search Tree

• tag: BST, recursion
• medium
• similar: XXX to BST

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

思路

• 一看就想到了sorted array to Binary Search Tree, 是pre-order recursion, 然后root就是mid.
• 但是这里是list, 这样做的话, 每次都要loop一遍, 找middle node. 就变成了O(n^2)了.
• 其实使用in-order来做.

解法1: (我最开始的想法)

• 直接套用sorted array to Binary Search Tree来做, O(N^2).
• 代码如下:

解法2:

• 可以使用in-order来做. 因为in-order和list的正常遍历的顺序是一样的->只要next即可.
• 看来以前对in-order recursion还没有完全掌握.
• 参考的: leetcode discussion解法
• 代码如下:

  private ListNode node;
  public TreeNode sortedListToBST(ListNode head) {
    if (head == null)  return null;
    int size = 0;
    ListNode runner = head;
    node = head;

    while (runner != null) {
      runner = runner.next;
      size++;
    }

    return helper(0, size-1);
  }

  /**
   * https://leetcode.com/discuss/23676/share-my-o-1-space-and-o-n-time-java-code
   * @param start
   * @param end
   * @return
   */
  private TreeNode helper(int start, int end) {
    if (start > end)  return null;
    int mid = start + (end-start)/2;
    TreeNode left = helper(start, mid-1);

    TreeNode root = new TreeNode(node.val);
    root.left = left;
    node = node.next; // 关键点!!! 正是利用了in-order~list的遍历, 使得O(logN)!!!

    TreeNode right = helper(mid+1, end);
    root.right = right;

    return root;
  }

反思

• 要深入理解各种recursion. 以及各种数据结构之间的关系. 例如这里就是list=>tree的in-order traversal. 还有graph的pre/post/reverse...
• 根据数据结构的不同, 同类型题目的解法也会变化.
• list的recursion有时候会根据长度来找中间点, 所以recursion的参数是start, end