本文主要是介绍LeetCode 题解(154): 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.
题解:
递归。
C++版:
class Solution {
public:TreeNode* sortedListToBST(ListNode* head) {if(!head)return NULL;int length = 0;ListNode* p = head;while(p) {p = p->next;length++;}return toBST(head, length);}ListNode* findMid(ListNode* head, int pos) {ListNode* p = head;int i = 0;while(i < pos) {p = p->next;i++;}return p;}TreeNode* toBST(ListNode* head, int length) {if(length == 0) {return NULL;}else if(length == 1) {TreeNode* root = new TreeNode(head->val);return root;} else {ListNode* mid = findMid(head, (length - 1) / 2);TreeNode* root = new TreeNode(mid->val);root->left = toBST(head, (length- 1) / 2);root->right = toBST(mid->next, length - (length + 1) / 2);return root;}}
};
Java版:
public class Solution {public TreeNode sortedListToBST(ListNode head) {int length = 0;ListNode p = head;while(p != null) {p = p.next;length++;}return toBST(head, length);}public TreeNode toBST(ListNode head, int length) {if(length == 0) {return null;} else if(length == 1) {return new TreeNode(head.val);} else {ListNode mid = findMid(head, length);TreeNode root = new TreeNode(mid.val);root.left = toBST(head, (length - 1) / 2);root.right = toBST(mid.next, length - (length + 1) / 2);return root;}}public ListNode findMid(ListNode head, int length) {ListNode p = head;int i = 0;while(i < (length - 1) / 2) {p = p.next;i++;}return p;}
}
Python版:
class Solution:# @param {ListNode} head# @return {TreeNode}def sortedListToBST(self, head):length = 0p = headwhile p != None:p = p.nextlength += 1return self.toBST(head, length)def toBST(self, head, length):if length == 0:return Noneelif length == 1:return TreeNode(head.val)else:mid = self.findMid(head, length)root = TreeNode(mid.val)root.left = self.toBST(head, (length - 1) / 2)root.right = self.toBST(mid.next, length - (length + 1) / 2)return rootdef findMid(self, head, length):p, i = head, 0while i < (length - 1) / 2:p = p.nexti += 1return p
这篇关于LeetCode 题解(154): Convert Sorted List to Binary Search Tree的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!