Leetcode: Convert Sorted List to Binary Search Tree. java
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
每次取链表的中点作为root,然后递归
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; next = null; } * } */ /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode sortedListToBST(ListNode head) { if (head == null) return null; if (head.next == null) return new TreeNode(head.val); //p为链表中点,从p处截断,右半头节点为q ListNode p = getMid(head); ListNode q = p.next; p.next = null; TreeNode root = new TreeNode(p.val); //删除p 新建一个虚拟的节点r r.next是左半段的头节点 ListNode r = new ListNode(0); r.next = head; ListNode s = r; while (true) { if (s.next == p) break; s = s.next; } s.next = null; //递归 root.left = sortedListToBST(r.next); root.right = sortedListToBST(q); return root; } public ListNode getMid(ListNode head) { if (head == null || head.next == null) return head; ListNode p = head; ListNode q = head; while (p.next != null && q.next != null && q.next.next != null) { p = p.next; q = q.next.next; } return p; } }
Leetcode: Convert Sorted List to Binary Search Tree. java,古老的榕树,5-wow.com
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。