Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Example
Tags Expand
解题思路:
思路一:平衡树调整。第一步建立一个单向树,然后使用平衡树的调整。逻辑比较绕,虽然完成了代码,但是大数据时,测试超时。
思路二:保存所有节点到数组(List集合),然后使用二分法,依次建立所有的头节点和左子树,右子树。
思路三:参考网上解法,核心还是使用二分法,但是比较巧妙的一点是在确定所有元素个数和划分左右子树后,能够实现指针的一次遍历,读取全部数据,无需多次将数据读出保存。
思路一:
/** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param head: The first node of linked list. * @return: a tree node */ public TreeNode sortedListToBST(ListNode head) { if (head == null) return null; TreeNode root = null; while (head != null) { int v = head.val; head = head.next; TreeNode node = new TreeNode(v); node.left = root; root = node; } return adjustNode(root); } TreeNode adjustNode(TreeNode node) { if (node != null) { int l = getLevel(node.left); int r = getLevel(node.right); while (l - r >= 2) { TreeNode tmp = node.left; if (tmp.right == null) { node.left = null; tmp.right = node; node = tmp; } else { TreeNode lmax = tmp.right; while (lmax.right != null) { tmp = lmax; lmax = lmax.right; } tmp.right = null; lmax.left = node.left; lmax.right = node; node.left = null; node = lmax; } l = getLevel(node.left); r = getLevel(node.right); } while (r - l >= 2) { TreeNode tmp = node.right; if (tmp.left == null) { node.right = null; tmp.left = node; node = tmp; } else { TreeNode lmax = tmp.left; while (lmax.left != null) { tmp = lmax; lmax = lmax.left; } tmp.left = null; lmax.right = node.right; lmax.left = node; node.right = null; node = lmax; } l = getLevel(node.left); r = getLevel(node.right); } node.left = adjustNode(node.left); node.right = adjustNode(node.right); } return node; } int getLevel(TreeNode node) { if (node == null) return 0; else return Math.max(getLevel(node.left) + 1, getLevel(node.right) + 1); } }
解法二:
/** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param head: The first node of linked list. * @return: a tree node */ public TreeNode sortedListToBST(ListNode head) { if (head == null) return null; ArrayList<Integer> list = new ArrayList<Integer>(); while (head != null) { list.add(head.val); head = head.next; } TreeNode root = getNode(list, 0, list.size() - 1); return root; } private TreeNode getNode(ArrayList<Integer> list, int x1, int x2) { if (x1 == x2) return new TreeNode(list.get(x1)); else if (x1 > x2) return null; else { int mid = (x1 + x2) / 2; TreeNode node = new TreeNode(list.get(mid)); node.left = getNode(list, x1, mid - 1); node.right = getNode(list, mid + 1, x2); return node; } } }
思路三:(网上解法)
public TreeNode sortedListToBST(ListNode head) { if(head == null) return null; ListNode cur = head; int count = 0; while(cur!=null) { cur = cur.next; count++; } ArrayList<ListNode> list = new ArrayList<ListNode>(); list.add(head); return helper(list,0,count-1); } private TreeNode helper(ArrayList<ListNode> list, int l, int r) { if(l>r) return null; int m = (l+r)/2; TreeNode left = helper(list,l,m-1); TreeNode root = new TreeNode(list.get(0).val); root.left = left; list.set(0,list.get(0).next); root.right = helper(list,m+1,r); return root; }