首页 > 代码库 > [Leetcode] Convert Sorted List to Binary Search Tree
[Leetcode] 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.
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; next = null; } 7 * } 8 */ 9 /**10 * Definition for binary tree11 * public class TreeNode {12 * int val;13 * TreeNode left;14 * TreeNode right;15 * TreeNode(int x) { val = x; }16 * }17 */18 public class Solution {19 public TreeNode sortedListToBST(ListNode head) {20 return mySortedListToBST(head, getLength(head));21 }22 23 private TreeNode mySortedListToBST(ListNode head, int length) {24 // TODO Auto-generated method stub25 if (head == null || length == 0)26 return null;27 if (length == 1)28 return new TreeNode(head.val);29 int mid = length / 2;30 ListNode peak = head;31 for (int i = 0; i < mid; ++i) {32 peak = peak.next;33 }34 TreeNode root=new TreeNode(peak.val);35 root.left=mySortedListToBST(head, mid);36 root.right=mySortedListToBST(peak.next, length-mid-1);37 return root;38 }39 40 private int getLength(ListNode head) {41 // TODO Auto-generated method stub42 int length = 0;43 while (head != null) {44 head = head.next;45 length++;46 }47 return length;48 }49 }
[Leetcode] Convert Sorted List to Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。