[LeetCode]109. Convert Sorted List to Binary Search Tree

Problem

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,-3,9,-10,null,5], which represents the following height balanced BST:

1
2
3
4
5
     0
/ \
-3 9
/ /
-10 5

Solution

解析

将一个有序链表转换成一个二叉搜索树。二叉搜索树性质,如果根节点的左子树存在,那么左子树节点的值都小于等根节点的值;如果右子树存在,右子树节点的值都大于根节点的值。

由于树的递归定义,这里使用递归方法进行求解。先找到有序链表的中间节点,创建一个根节点,然后依据中间节点将链表划分成两部分,中间节点左边为左子树,右边为右子树,递归调用函数,生成最终结果。

终止条件是:为空,返回nullptr;长度为1,创建一个单节点树。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* 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) return nullptr;
if (!head->next) return new TreeNode(head->val);

ListNode *slow = head, *fast = head, *last = slow;

while (fast && fast->next){
last = slow;
slow = slow->next;
fast = fast->next->next;
}
last->next = nullptr;
fast = slow->next;

TreeNode* root = new TreeNode(slow->val);
root->left = sortedListToBST(head);
root->right = sortedListToBST(fast);

return root;
}
};
您的支持就是我更新的最大动力!谢谢!