c/c++开发分享C++实现LeetCode(109.将有序链表转为二叉搜索树)

[leetcode] 109.convert sorted list to binary search tree 将有序链表转为二叉搜索树given a singly linked list wher


[leetcode] 109.convert sorted list to binary search tree 将有序链表转为二叉搜索

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

这道题是要求把有序链表转为二叉搜索树,和之前那道 convert sorted array to binary search tree 思路完全一样,只不过是操作的数据类型有所差别,一个是数组,一个是链表。数组方便就方便在可以通过index直接访问任意一个元素,而链表不行。由于二分查找法每次需要找到中点,而链表的查找中间点可以通过快慢指针来操作,可参见之前的两篇博客 reorder list 和 linked list cycle ii 有关快慢指针的应用。找到中点后,要以中点的值建立一个数的根节点,然后需要把原链表断开,分为前后两个链表,都不能包含原中节点,然后再分别对这两个链表递归调用原函数,分别连上左右子节点即可。代码如下:

解法一:

  class solution {  public:      treenode *sortedlisttobst(listnode* head) {          if (!head) return null;          if (!head->next) return new treenode(head->val);          listnode *slow = head, *fast = head, *last = slow;          while (fast->next && fast->next->next) {              last = slow;              slow = slow->next;              fast = fast->next->next;          }          fast = slow->next;          last->next = null;          treenode *cur = new treenode(slow->val);          if (head != slow) cur->left = sortedlisttobst(head);          cur->right = sortedlisttobst(fast);          return cur;      }  };

我们也可以采用如下的递归方法,重写一个递归函数,有两个输入参数,子链表的起点和终点,因为知道了这两个点,链表的范围就可以确定了,而直接将中间部分转换为二叉搜索树即可,递归函数中的内容跟上面解法中的极其相似,参见代码如下:

解法二:

  class solution {  public:      treenode* sortedlisttobst(listnode* head) {          if (!head) return null;          return helper(head, null);      }      treenode* helper(listnode* head, listnode* tail) {          if (head == tail) return null;          listnode *slow = head, *fast = head;          while (fast != tail && fast->next != tail) {              slow = slow->next;              fast = fast->next->next;          }          treenode *cur = new treenode(slow->val);          cur->left = helper(head, slow);          cur->right = helper(slow->next, tail);          return cur;      }  };

类似题目:

convert sorted array to binary search tree

参考资料:

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35476/share-my-java-solution-1ms-very-short-and-concise.

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35470/recursive-bst-construction-using-slow-fast-traversal-on-linked-list

到此这篇关于c++实现leetcode(109.将有序链表转为二叉搜索树)的文章就介绍到这了,更多相关c++实现将有序链表转为二叉搜索树内容请搜索<猴子技术宅>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<猴子技术宅>!

需要了解更多c/c++开发分享C++实现LeetCode(109.将有序链表转为二叉搜索树),都可以关注C/C++技术分享栏目—猴子技术宅(www.ssfiction.com)

本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ssfiction.com/c-cyuyankaifa/676116.html

发表评论

邮箱地址不会被公开。 必填项已用*标注