109. 有序链表转换二叉搜索树

109. 有序链表转换二叉搜索树

转为数组后再转

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> nodes;
        while(head)
        {
            nodes.push_back(head->val);
            head = head->next;
        }
        return build(nodes, 0, nodes.size() - 1);
    }
private:
    TreeNode* build(vector<int>& nodes, int lo, int hi)
    {
        if(lo > hi)
            return nullptr;
        auto mid = lo + ((hi - lo) >> 1);
        TreeNode* node = new TreeNode(nodes[mid]);
        node->left = build(nodes, lo, mid - 1);
        node->right = build(nodes, mid + 1, hi);
        return node;
    }
};

T(n) : O(n)

S(n) : O(n) + O(logn)(递归栈)

直接使用链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        return build(head, nullptr);
    }
private:
    TreeNode* build(ListNode* begin, ListNode* end)
    {
        // 如果mid的右边没有元素，那是不可能的，因为这说明walker走到了最右边，不可能
        // 如果mid的右边只有一个元素，在下次取右半边时候，由于取mid—>next，则右边会返回nullptr
        // 如果右边两个元素及以上，正常走
        // 如果左边没有元素，则下一回合左边begin==end，返回nullptr
        // 如果左边只有一个，下一回合会取左边那个元素，然后下一回合后的符合上述的情况
        // 如果左边两个元素及以上，正常走
        if(begin == end)
            return nullptr;
        auto mid = getMid(begin, end);
        TreeNode* node = new TreeNode(mid->val);
        node->left = build(begin, mid);
        // 重点处理 : 由于当begin和end相邻时会倾向于取begin这个元素，所以为了避免重复取，需要使mid右移一个。
        node->right = build(mid->next, end);
        return node;
    }
    // 借用链表取下一个元素方便的特性，设置为左闭右开，即无论什么情况下都不可能取到最右边的元素。
    ListNode* getMid(ListNode* begin, ListNode* end)
    {
        ListNode* walker = begin;
        ListNode* runner = begin;
        while(runner != end && runner->next != end)
        {
            runner = runner->next->next;
            walker = walker->next;
        }
        return walker;
    }
};

T(n) : O(nlogn)

S(n) : O(logn)(递归栈)

中序遍历+填充

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        return build(head, 0, getLength(head) - 1);
    }
private:
    int getLength(ListNode* head)
    {
        int ret = 0;
        for(; head; ++ret, head = head->next);
        return ret;
    }
    TreeNode* build(ListNode*& head, int lo, int hi)
    {
        if(lo > hi)
            return nullptr;
        auto mid = lo + (hi - lo) / 2;
        TreeNode* node = new TreeNode();
        node->left = build(head, lo, mid - 1);
        node->val = head->val;
        head = head->next;
        node->right = build(head, mid + 1, hi);
        return node;
    }
};