LeetCode-109-Convert Sorted List to Binary Search Tree

发布时间：2020-12-14 04:26:13 所属栏目：大数据来源：网络整理

导读：算法描述： Given a singly linked list where elements are sorted in ascending order,convert it to a height balanced BST. For this problem,a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of? e

算法描述：

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

For this problem,a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of?every?node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,5,9],One possible answer is: [0,9,-10,null,5],which represents the following height balanced BST:

      0
     /    -3   9
   /   /
 -10  5

解题思路：理解原理

    TreeNode* sortedListToBST(ListNode* head) {
        if(head == nullptr) return nullptr;
        return helper(head,nullptr);       
    }
    
    TreeNode* helper(ListNode* start,ListNode* end){
         if(start==end) return nullptr;
        ListNode* fast = start;
        ListNode* slow = start;
        while(fast->next!=end && fast->next->next!=end){
            fast = fast->next->next;
            slow = slow->next;
        }
        
        TreeNode* node = new TreeNode(slow->val);
        node->left = helper(start,slow);
        node->right = helper(slow->next,end);
        return node;
    }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!