Convert Sorted List to Binary Search Tree

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

导读：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

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,0,5,9],One possible answer is: [0,9,-10,null,5],which represents the following height balanced BST:

      0
     /    -3   9
   /   /
 -10  5

code

class Solution
{
public:
    TreeNode* sortedListToBST(ListNode* head)
    {
        if(head==nullptr)
            return nullptr;

        vector<int> res;
        auto tmp=head;
        while(tmp)
        {
            res.emplace_back(tmp->val);
            tmp=tmp->next;
        }
        return dfs(0,res.size()-1,res);
    }
private:
    TreeNode *dfs(int start,int end,vector<int>& res)
    {
        if(end<start)
            return nullptr;

        int index=(start+end)/2;
        TreeNode *root=new TreeNode(res.at(index));
        root->left=dfs(start,index-1,res);
        root->right=dfs(index+1,end,res);

        return root;
    }
};

（编辑：李大同）

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