【ATT】Convert Sorted List to Binary Search Tree

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

给定一个递增排序好的链表，将其转换成一个平衡的二叉查找树。

A: 这道题与“Convert Sorted Array to BST” 不同。数组随即访问的效率是O(1)，所以可以快速的找到中间元素，而链表随即访问的效率为O(n)，因此不同用之前的方法。

Top-down的方法不能用了，改用：bottom-up的方式建立BST。随着list的遍历，创建树的结点，避免了链表的随机访问。

同时，对任意结点，用begin，middle，end控制其左右子树的结点数目，=》 balanced BST

复杂度：O(N).

TreeNode *helper(ListNode *&list,int begin,int end) //注意list传递的是引用；用链表的长度做为递归的结束条件
    {
        if(begin>end)
            return NULL;
        int middle = begin + (end - begin)/2;
        TreeNode *leftChild = helper(list,begin,middle-1);
        TreeNode *parent = new TreeNode(list->val);
        parent->left = leftChild;
        list = list->next;                //list赋成下一个节点的地址。
        TreeNode *rightChild = helper(list,middle+1,end);
        parent->right = rightChild;
        return parent;
    }

    int getLength(ListNode *head)
    {
        ListNode *cur = head;
        int length = 0;
        while(cur!=NULL)
        {
            length++;
            cur = cur->next;
        }
        return length;
    }
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int length = getLength(head);
        return helper(head,0,length-1);
    }

原文链接: https://www.cnblogs.com/summer-zhou/archive/2013/06/04/3117219.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍