Dada una lista enlazada individual donde los elementos se ordenan en orden ascendente, conviértalo en un BST de altura equilibrada.
Pensamientos
Si le dan una matriz, el problema es bastante sencillo. Pero las cosas se complican un poco más cuando tienes una lista enlazada individualmente en lugar de una matriz. Ahora ya no tiene acceso aleatorio a un elemento en el tiempo O (1). Por lo tanto, debe crear nodos de abajo hacia arriba y asignarlos a sus padres. El enfoque de abajo hacia arriba nos permite acceder a la lista en su orden al mismo tiempo que se crean los nodos.
Solución Java
// Definition for singly-linked list. class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } // Definition for binary tree class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { static ListNode h; public TreeNode sortedListToBST(ListNode head) { if (head == null) return null; h = head; int len = getLength(head); return sortedListToBST(0, len - 1); } // get list length public int getLength(ListNode head) { int len = 0; ListNode p = head; while (p != null) { len++; p = p.next; } return len; } // build tree bottom-up public TreeNode sortedListToBST(int start, int end) { if (start > end) return null; // mid int mid = (start + end) / 2; TreeNode left = sortedListToBST(start, mid - 1); TreeNode root = new TreeNode(h.val); h = h.next; TreeNode right = sortedListToBST(mid + 1, end); root.left = left; root.right = right; return root; } } |
