【leetcode每日一题】NO109.Convert Sorted List to Binary Search Tree

Myth丶恋晨 2022-08-04 04:04 166阅读 0赞

题目：Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.给定一个升序排列的单链表，把它转化为一个搜索二叉树。

解析：搜索二叉树的左子节点要小于父节点，右子节点要大于父节点。单链表是升序的，先找出链表的中间节点，作为二叉树的根节点。然后再分别对左半链表和右半链表进行相同的操作。

代码：

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode *creatTree(ListNode *head,int left,int right)
        {
            if(left>right)
                return NULL;
            ListNode *temp=head;
            int middle=(left+right)/2;
            for(int i=left;i<middle;i++)
                temp=temp->next;
            TreeNode *leftNode=creatTree(head,left,middle-1);
            TreeNode *rightNode=creatTree(temp->next,middle+1,right);
            TreeNode *node=new TreeNode(temp->val);
            node->left=leftNode;
            node->right=rightNode;
            return node;
        }
        TreeNode *sortedListToBST(ListNode *head) {
            int len=0;
            ListNode *temp=head;
            while(temp!=0)
            {
                len++;
                temp=temp->next;
            }
            return creatTree(head,0,len-1);
        }
    };