首页 > 代码库 > Leetcode: Convert Sorted List to Binary Search Tree

Leetcode: Convert Sorted List to Binary Search Tree

2024-07-21 14:13:52   216人阅读

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

难度70，与Convert Sorted Array to Binary Search Tree问题相似，这道题的做法就是，我们需要中点来做每一层树的根，问题在于，对于一个链表我们是不能常量时间访问它的中间元素的。于是我的想法是花O(N)的时间把链表里面的元素先存到一个数组或者ArrayList里面，这样就有了一个sorted的数组或者ArrayList，我们就很容易对它递归来建立一个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         if (head == null) return null;21         ListNode dummy = new ListNode(-1);22         dummy.next = head;23         ListNode cursor = dummy;24         int count = 0;25         while (cursor.next != null) {26             count++;27             cursor = cursor.next;28         }29         int[] array = new int[count];30         cursor = dummy;31         for (int i = 0; i < count; i++) {32             array[i] = cursor.next.val;33             cursor = cursor.next;34         }35         TreeNode result = helper(array, 0, array.length - 1);36         return result;37     }38     39     public TreeNode helper(int[] array, int begin, int end) {40         if (begin > end) return null;41         if (begin == end) return new TreeNode(array[begin]);42         int mid = (begin + end) / 2;43         TreeNode root = new TreeNode(array[mid]);44         root.left = helper(array, begin, mid - 1);45         root.right = helper(array, mid + 1, end);46         return root;47     }48 }

用ArrayList的做法：

 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         if (head == null) return null;21         22         ArrayList<Integer> listNode = new ArrayList<Integer>();23         while(head != null){24             listNode.add(head.val);25             head = head.next;26         }27         int left = 0;28         int right= listNode.size()-1;29         return helper(listNode, left, right);30     }31     32     public TreeNode helper(ArrayList<Integer> listNode, int left, int right){33         if(left>right) return null;34         35         TreeNode node = new TreeNode(0);36         int mid = (left+right)/2;37         node.val = listNode.get(mid);38         node.left = helper(listNode, left, mid-1);39         node.right = helper(listNode, mid+1, right);            40         return node;41     }42 }

 

Leetcode: Convert Sorted List to Binary Search Tree


联系
我们