LeetCode刷题（C++）——Convert Sorted List to Binary Search Tree（Normal）

谁践踏了优雅 2022-06-15 23:30 130阅读 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 a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            if (head == NULL)
    			return NULL;
    		if (head->next == NULL)
    			return new TreeNode(head->val);
    		ListNode prenode(0);
    		ListNode* pre = &prenode;
    		pre->next = head;
    		ListNode* one = head;               //用来循环指向中间结点，即子树根结点
    		ListNode* two = head;
    		while (two && two->next)            //查找子树根结点
    		{
    			pre = pre->next;
    			one = one->next;
    			two = two->next->next;
    		}
    		TreeNode* root = new TreeNode(one->val);
    		ListNode* temp = one->next;
    		pre->next = NULL;                          //将左子树和根结点断开
    		one->next = NULL;                          //将右子树和根结点断开
    		root->left = sortedListToBST(head);
    		root->right = sortedListToBST(temp);
    		return root;
        }
    };