leetcode 109 升序链表建立AVL树

原题传送门—>>

Given the head of 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 1:

• Input: head = [-10,-3,0,5,9]
• Output: [0,-3,9,-10,null,5]
• Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:

• Input: head = []
• Output: []

Example 3:

• Input: head = [0]
• Output: [0]

Example 4:

• Input: head = [1,3]
• Output: [3,1]

链表与数组定义：

/**
 * 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) {}
 * };
 */

方案1 数组法：

（就是无脑但复杂度还挺低🐶）

class Solution {
public:
    vector<int> nodes;
    TreeNode* sortedListToBST(ListNode* head) {
        ListNode* p = head;
        while(p)
        {
            nodes.push_back(p->val);
            p = p->next;
        }
        return buildBST(0, nodes.size() - 1);
    }
    TreeNode* buildBST(int start, int end)
    {
        if(start > end)
            return NULL;
        int mid = (start + end) / 2;
        TreeNode* base = new TreeNode(nodes[mid]);
        base->left = buildBST(start, mid - 1);
        base->right = buildBST(mid + 1, end);
        return base;
    }
};

时间复杂度O (N)
空间复杂度O（N）

方案2 快慢指针法

关于快慢指针法的应用，请戳：《快慢指针法L》

思路仍然是不变的：在链表中找到中位数作为根，然后分别建立左右子树
区别是如何找中位数？ 方案1中采取了用向量存储链表。
本方案采取快慢指针法定位中位数。
定义一个快指针，每次循环前进2个结点
一个慢指针，每次循环前进1个结点
那么，当快指针到达链表尾部，慢指针大概到达了链表中间位置。

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        return sortedListToBST(head, NULL);
    }
    TreeNode* sortedListToBST(ListNode* head, ListNode* rear)
    {
        if(head == rear)
            return NULL;
        if(head->next == rear)
        {
            return new TreeNode(head->val);
        }
        ListNode* fastPtr = head, *slowPtr = head;
        while((fastPtr != rear) && (fastPtr->next != rear))
        {
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }
        TreeNode* root = new TreeNode(slowPtr->val);
        root->left = sortedListToBST(head, slowPtr);
        root->right = sortedListToBST(slowPtr->next, rear);
    return root;
    }
};

时间复杂度 O(NlogN)
空间复杂度 O(1)

方案3 由中序遍历查找树产生的灵感

查找二叉树的重要特点是：中序遍历的结果为升序。
用中序遍历的方式来建立树，得到的就是搜索树。
但还要保证一个问题：左右子树的结点尽可能相等。所以还需要求得链表长度，逐步二分进行递归

class Solution {
public:
    ListNode* p;
    TreeNode* sortedListToBST(ListNode* head) {
        int len = 0;
        p = head;
        while(p)
        {
            p = p->next;
            ++len;
        }
        p = head;
        return creatTree(len);
    }
    TreeNode* creatTree(int n)
    {
        if(!n)
            return NULL;
        int mid = n / 2;
        TreeNode* left = creatTree(mid);
        TreeNode* root = new TreeNode(p->val);
        p = p->next;
        TreeNode* right = creatTree(n - mid - 1);
        root->left = left;
        root->right = right;
        return root;
    }
};

时间复杂度O(N)
空间复杂度O(log(N))