Convert Sorted List to Binary Search Tree

Posted by: lexigrey on: November 23, 2013

• In: leetcode
• 7 Comments

思路：

1. 因为没有random access，所以用in order的方式，一个一个遍历element，然后assign给parent
2. 平时正常array convert bst都是用pre order的方式，root算好，然后left=.., right =…
3. 一般你做树的bottom up是post order，left做出来，right做出来，root取决于这两个值
4. 这里为什么要in order呢？ 左，中，右的方式，正好是sorted。所以每次做完子树，然后下一个节点就是下一个位置。但是什么时候是个头呢，因为h.next会一直存在的，但是你的子树怎么知道什么时候返回到上一层？所以就要用p, q两个指针了，p代表当前sub list的头，q是尾。但是不要真的用他们来random access，就是用来stop就行了。

public TreeNode sortedListToBST(ListNode head) {
    int len = 0;
    ListNode dummy = head;
    while (dummy != null) {
       len++;
    dummy = dummy.next;
    }
    ListNode[] curr = new ListNode[1];
    curr[0] = head;
    return convert(curr, 0, len - 1);
}
private TreeNode convert(ListNode[] curr, int p, int q) {
    if (p > q)
        return null;
    int mid = (p + q) / 2;
    TreeNode left = convert(curr, p, mid - 1);
    TreeNode root = new TreeNode(curr[0].val);
    curr[0] = curr[0].next;
    TreeNode right = convert(curr, mid + 1, q);
    root.left = left;
    root.right = right;
    return root;
}

Tags: hard, list, tree, 中序