LeetCode 109 每日一题 Day32.

今天的结果非常amazing

这个月的主题是二叉树，这道题是平衡二叉树和搜索二叉树的结合，没记错的话应该叫AVL平衡二叉树
用二分法的思想，将整棵树分为“根”,"左子树”,"右子树"三个部分，将中间的节点作为根，左右子树有分别取出中间的作为根，进行递归，比较简单。
题目中给出的有序表是自己实现的有序表，为了方便我将其转化成了vector存储。

再多的也没什么了，去看看和官方题解还有什么方法

class Solution {
public:
    vector<int> list;
    TreeNode* sortedListToBST(ListNode* head) {
        if(head==nullptr) return nullptr;
        while(head!=nullptr)
        {
            list.push_back(head->val);
            head=head->next;
        }
        int n=list.size();
        int mid=(n-1)/2;
        TreeNode* root=new TreeNode(list[mid]);
        bs(0,mid-1,root,true);
        bs(mid+1,n-1,root,false);
        return root;
    }
    void bs(int begin,int end,TreeNode* &root,bool side)
    {
        if(end<begin)
            return;
        int mid=(end-begin)/2+begin;
        if(side){
            root->left=new TreeNode(list[mid]);
            bs(begin,mid-1,root->left,true);
            bs(mid+1,end,root->left,false);
        }
        else{
            root->right=new TreeNode(list[mid]);
            bs(begin,mid-1,root->right,true);
            bs(mid+1,end,root->right,false);
        }
    }
};