leetcode 108. Convert Sorted Array to Binary Search Tree 、109. Convert Sorted List to Binary Search Tree

108. Convert Sorted Array to Binary Search Tree

这个题使用二分查找，主要要注意边界条件。

如果left > right，就返回NULL。每次更新的时候是mid-1，mid+1。

自己推一下基本就可以验证了。

class Solution {

public:

    TreeNode* sortedArrayToBST(vector<int>& nums) {

        return ToBST(nums,,nums.size() - );

    }

    TreeNode* ToBST(vector<int>& nums,int start,int end){

        if(start > end)

            return NULL;

        int mid = start + (end - start)/;

        TreeNode* root = new TreeNode(nums[mid]);

        root->left = ToBST(nums,start,mid-);

        root->right = ToBST(nums,mid+,end);

        return root;

    }

};

109. Convert Sorted List to Binary Search Tree

https://www.cnblogs.com/grandyang/p/4295618.html

这个题还是用二分查找，每次用双指针找中间的位置，然后递归。

注意end节点是NULL，并且每次中间的位置mid也会成为左子树的end节点。

class Solution {

public:

    TreeNode* sortedListToBST(ListNode* head) {

        return sortedList(head,NULL);

    }

    TreeNode* sortedList(ListNode* start,ListNode* end){

        if(start == end)

            return NULL;

        ListNode* slow = start;

        ListNode* fast = start;

        while(fast->next != end && fast->next->next != end){

            slow = slow->next;

            fast = fast->next->next;

        }

        TreeNode* mid = new TreeNode(slow->val);

        mid->left = sortedList(start,slow);

        mid->right = sortedList(slow->next,end);

        return mid;

    }

};

巴特西

leetcode 108. Convert Sorted Array to Binary Search Tree 、109. Convert Sorted List to Binary Search Tree

最新文章

热门文章