`
huntfor
  • 浏览: 194243 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Convert Sorted List to Binary Search Tree

 
阅读更多

新博文地址:[leetcode]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.

 跟这道题很相似,没道理没写博文啊(= =//)算了,反正也简单,道理也一样,简单说一下吧。

这道题要求高度balance,因此可以考虑采取二分法,每次找到链表的中点,左边的一半生成左子树,右边的是右子树,这样就能够达到平衡了。但是链表如何能找到中点呢?顺序查找肯定啦。

但是不知道大家对快慢指针是否熟悉:

找中间节点 
快指针每次走两步,慢指针每次走一步,当快指针走到头,慢指针刚好走到一半,当然有一些边界情况需要考虑,比如链表就一个节点的情况等等。

 

找到了中间节点之后呢?

前面说了左边一半是左子树,右边是右子树。因此我们要根据中间节点将原链表分裂,因此我们还需要找到中间节点的前驱节点preMid,并将preMid.next = null,这样head就代表了左子树,mid.next 就是右子树,递归。

 

代码如下:

	public TreeNode sortedListToBST(ListNode head) {
		if(head == null){
			return null;
		}		
		ListNode mid = getMidNode(head);
		ListNode preMid = head;
		if(mid != head){//找mid的前驱节点
			while(preMid.next != mid){
				preMid = preMid.next;
			}
		}else{
			head = null;//当mid就是head节点时,即表示左子树为空了
		}
		preMid.next = null;//截断之后,head 表示左子树
		ListNode rightHead = mid.next;
		TreeNode root = new TreeNode(mid.val);
		root.left = sortedListToBST(head);
		root.right = sortedListToBST(rightHead);
		return root;
	}

	private ListNode getMidNode(ListNode head){
		if(head == null){
			return null;
		}
		ListNode fast = head;
		ListNode slow = head;
		while(fast != null && fast.next != null){
			try{
				fast = fast.next.next;
			}catch(NullPointerException e){
				return slow;
			}
			slow = slow.next;
		}
		return slow;
	}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics