首页 > 代码库 > 【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.
题解:开始想到的方法比较偷懒,直接遍历一遍数组,把每个ListNode对应的值放到数组里面,然后把数组转换成BST,想来这个题的本意肯定不是这样。
自己也想到了bottom-up的方法,但是没想明白怎么个bottom-up法,真的是昨天做梦都在想=。=
今天早上终于弄懂了,用递归,不过这个递归比较难理解。
递归函数的定义是这样的 public TreeNode sortLisTreeNodeRecur(int size) ,参数size的意义可以理解为要建立的树的节点个数。用一个current变量作为linked list的游标。递归函数的实现如下:
1 public TreeNode sortLisTreeNodeRecur(int size){ 2 if(size <= 0) 3 return null; 4 5 TreeNode left = sortLisTreeNodeRecur(size/2); 6 TreeNode root = new TreeNode(current.val); 7 current = current.next; 8 TreeNode right = sortLisTreeNodeRecur(size - size/2 - 1); 9 10 root.left = left;11 root.right = right;12 13 return root;14 }
可以看到,它先递归调用自己建立整个左子树,在这个过程中,current作为全局私有变量,在左子树建立完成以后,就自动移动到根节点对应的ListNode处了,所以建立完左子树后建立根节点,后移current,然后递归的建立整个右子树。
以Linked List = 1->2->3->4->5来画图说明:
代码如下:
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; next = null; } 7 * } 8 */ 9 /**10 * Definition for binary tree11 * public class TreeNode {12 * int val;13 * TreeNode left;14 * TreeNode right;15 * TreeNode(int x) { val = x; }16 * }17 */18 public class Solution {19 private ListNode current;20 public int getLength(ListNode head){21 int answer = 0;22 while(head != null){23 answer++;24 head = head.next;25 }26 27 return answer;28 }29 public TreeNode sortLisTreeNodeRecur(int size){30 if(size <= 0)31 return null;32 33 TreeNode left = sortLisTreeNodeRecur(size/2);34 TreeNode root = new TreeNode(current.val);35 current = current.next;36 TreeNode right = sortLisTreeNodeRecur(size - size/2 - 1);37 38 root.left = left;39 root.right = right;40 41 return root;42 }43 public TreeNode sortedListToBST(ListNode head) {44 current = head;45 int size = getLength(head);46 return sortLisTreeNodeRecur(size);47 }48 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。