博文中会简要介绍Leetcode P0109题目分析及解题思路。
“Convert Sorted List to Binary Search Tree”是p0108的变形题，运用了深度优先搜索，这里也递归回溯的思路，借鉴了类似归并排序的思想。
Given the head of 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.
这道题的难点在于链表不能像数组一样完成随机访问，所以在解法里我们利用了快慢指针的想法，慢指针右移一位而快指针右移两位，这样我们就可以找到中点，同时我们也要维护一个prev指针用于标记左边链表的尾指针。
当任意一个指针为null时，就相当于在数组中left和right指针交错，这个时候搜索完毕，回溯即可。
以下是Java的题解代码实现。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null)
return null;
ListNode tail = head;
while (tail.next != null)
tail = tail.next;
return this.build(head, tail);
}
private TreeNode build(ListNode left, ListNode right) {
// 头尾指针都是null，所以在left指针之前或者right指针之后都会是null
if (left == null || right == null)
return null;
if (left == right)
return new TreeNode(left.val);
// Partition
ListNode prev = null, slow = left, fast = left.next;
// 这里快慢指针，当快指针移动到尾指针后的null时，slow恰好是中点
// 若快指针恰好移动到尾指针时，说明偶数个nodes，此时slow是左中点
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
if (prev != null)
prev.next = null;
TreeNode root = new TreeNode(slow.val);
root.left = this.build(left, prev);
root.right = this.build(slow.next, right);
return root;
}
}
以下是C++的题解代码实现。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if (!head)
return NULL;
ListNode *tail = head;
while (tail->next)
tail = tail->next;
return this->Build(head, tail);
}
private:
TreeNode* Build(ListNode *left, ListNode *right) {
if (!left || !right)
return NULL;
if (left == right)
return new TreeNode(left->val);
// Partition
ListNode *prev = NULL, *slow = left, *fast = left->next;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
if (prev)
prev->next = NULL;
TreeNode *root = new TreeNode(slow->val);
root->left = this->Build(left, prev);
root->right = this->Build(slow->next, right);
return root;
}
};