首页 > 代码库 > Convert Sorted List to Binary Search Tree
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.
首先想到的是先将单链表转化为数组,就可以取中位数为根节点再递归左右子做,时间复杂度O(n),空间复杂度O(n)。
在网上搜了个时间复杂度为O(n),空间复杂度为O(1)的做法,思路如下:
由于二叉排序树的中序遍历即有序,也就是与本题中的单链表从头到尾遍历相同,所以可以按照类似中序遍历的做法,首先,创建当前节点的左子,然后创建当前节点,将该节点的left指针指向之前创建好的左子,然后创建右子,以这样的顺序,每次新创建的节点都对应单链表的顺序遍历中当前位置的节点,因此,用一个全局遍历表示当链表,在递归过程中不断修改当前单链表的指针,使每次创建的节点与单链表头节点对应。代码如下:
1 public ListNode head; 2 public TreeNode sortedListToBST(ListNode head) { 3 this.head = head; 4 ListNode p = head; 5 int len = 0; 6 while (p != null) { 7 p = p.next; 8 len++; 9 } 10 return buildTree(0, len - 1); 11 } 12 13 private TreeNode buildTree(int start, int end) { 14 // TODO Auto-generated method stub 15 if (start > end) { 16 return null; 17 } 18 int mid = start + (end - start) / 2; 19 TreeNode left = buildTree(start, mid - 1); 20 TreeNode root = new TreeNode(head.val); 21 root.left = left; 22 head = head.next; 23 root.right = buildTree(mid + 1, end); 24 return root; 25 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。