首页 > 代码库 > 【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.
【解析】
分治:用快慢指针找到链表的中点,作为树的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); if (head.next.next == null) { TreeNode root = new TreeNode(head.val); root.right = new TreeNode(head.next.val); return root; } ListNode fast = head; ListNode slow = head; ListNode preSlow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; preSlow = slow; slow = slow.next; } ListNode mid = slow; preSlow.next = null; //make the first part end!!! TreeNode root = new TreeNode(mid.val); root.left = sortedListToBST(head); root.right = sortedListToBST(mid.next); return root; } }
容易出错的地方是,中点之前的链表结尾要设为null,表示该链表的结束。
【LeetCode】Convert Sorted List to Binary Search Tree 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。