LeetCode 109 有序链表转换成二叉搜索树

• 思路

    利用快慢指针找到链表中间节点位置，递归的建立左子树（注意建立左子树时的条件，不加语句是有问题的，考虑会出现什么问题？？？？）和右子树。代码如下：

• 代码

/*** 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 {
private:void buildTree(TreeNode*& root, ListNode* head){if(head == nullptr) return;ListNode* fast = head;ListNode* low = head;     ListNode* low_pre = nullptr;while(fast != nullptr && fast -> next != nullptr && fast -> next -> next != nullptr){//双指针找中间节点low_pre = low;fast = fast -> next -> next;low = low -> next;}root = new TreeNode(low -> val); buildTree(root -> right, low -> next);//建立右子树 if(head != low){//不加这个判断会一直递归下去，导致超时            if(low_pre != nullptr)low_pre -> next = nullptr;buildTree(root -> left, head);//建立左子树}}
public:TreeNode* sortedListToBST(ListNode* head) {TreeNode* root = nullptr;buildTree(root, head);return root;}
};