Wednesday, November 19, 2014

Convert sorted list to binary search tree

Leetcode link.

The way I handle this question is I first count how many nodes there are in the list, and construct an empty binary search tree, then use morris traversal/recursive inorder traversal to fill the whole tree with list value. Time complexity is O(n) with space complexity O(n).

But geekforgeek provided another brilliant solution. I am still pondering on why this works, and my bet is on the similarity between dfs and inorder traversal. But here is the code and some comments:
TreeNode* helper(ListNode* &head, int low, int high) {
    if(low == high) {
        TreeNode* ret = new TreeNode(head->val);
        head = head->next;
        return ret;
    }
    else if(low > high) return NULL;
    int mid = low + ((high-low)>>1);
    TreeNode* left = helper(head, low, mid-1);
    TreeNode* ret = new TreeNode(head->val);
    ret->left = left;
    head = head->next;
    ret->right = helper(head, mid+1, high);
    return ret;
}

TreeNode *sortedListToBST(ListNode *head) {
    if(!head) return NULL;
    ListNode* walker = head;
    int count = 0;
    while(walker) {
        ++count;
        walker = walker->next;
    }
    return helper(head, 0, count-1);
} 

That low and high index is quite confusing, they actually only represents how many nodes there are in this section. For each valid loop (\( low <= high \)) we need to make sure the list pointer moves to the next section once the root node for this section is handled, such that when we reaches line 13 list pointer is at the start of this section.
Anyway, this is the first time I see code that build a tree from leaf nodes. Very brilliant idea.

PS: geekforgeeks' code is actually even better than mine since the case when \(low == high\) is integrated in the ensuing code.

No comments:

Post a Comment