LeetCode109 Convert Sorted List to Binary Search Tree 解题报告

By | 19/03/2018

【题目】:

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:

      0
     / \
   -3   9
   /   /
 -10  5

意思就是将给定的排序好的链表转换成一个棵搜索二叉树,返回其中的一种情况

【Code】:

class Solution {
public:
 TreeNode* sortedListToBST(ListNode* head) {
 return func(head,NULL); 
 }
 TreeNode* func(ListNode* head,ListNode* tail){
 ListNode* fast = head;
 ListNode* slow = head;
 if(head == tail){
 return NULL;
 }
 while(fast!=tail&&fast->next!=tail){
 fast = fast->next->next;
 slow = slow->next;
 }
 TreeNode* root = new TreeNode(slow->val);
 root->left = func(head, slow);
 root->right = func(slow->next,tail);
 return root;
 }
};

【遇到的问题和解决办法】:

这个题目的难点在于不知道中点该怎么巧妙的去找,如果每一次都是根据数字的一半去找的花还要进行一道运算而且规模大的花这样硬算很容易出现一些小问题,因此,我们可以利用寻找倒数第K个节点中的办法,规定两个指针,然后fast每一次走的单位个数是slow的两倍,也就是大家一开始都在head 然后fast走两步,以后在到达尾节点之前的遍历中fast指向next的next而slow只是指向自己的next,还有就是while里面的调节一定是fast的因为他是快的那个所以fast的下一下不能为tail因此倒数两个都不能是fast,这么做的原因是fast一下条两个,在这个临界值的时候下一个状态就是最后一个tail节点了,嗯应该懂了吧。

 

如果这篇文章对你有帮助,欢迎buy my a coffe:

发表评论