现在的位置: 首页 > 综合 > 正文

Leetcode Convert Sorted List to Binary Search Tree

2014年04月05日 ⁄ 综合 ⁄ 共 717字 ⁄ 字号 评论关闭

Convert Sorted List to Binary Search Tree

 Total Accepted: 6119 Total
Submissions: 22895
My Submissions

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

二分法和中序遍历二叉树的高级结合应用。综合难度指数五星级。

难点:

1 如何设计二分法的结束条件?

2 如何中序先构造左子树,然后构造根节点,然后是右子树?

3 如何确定根节点?

4 如何返回节点,如何确定返回的节点是左子树还是右子树?

5 什么时候递归?

好多问题的一个算法设计,但是只要理解透切了,一切问题都可以归结为几行简单的代码。

这也叫做编程之美。

//2014-2-16 update
	TreeNode *sortedListToBST(ListNode *head) 
	{
		int n = getLength(head);
		return toBST(head, 0, n-1);
	}
	int getLength(ListNode *h)
	{
		int n = 0;
		for ( ; h; n++) h = h->next;
		return n;
	}
	TreeNode *toBST(ListNode *&h, int low, int up)
	{
		if (low > up) return nullptr;
		int m = low + ((up-low)>>1);

		TreeNode *lt = toBST(h, low, m-1);
		TreeNode *r = new TreeNode(h->val);
		h = h->next;
		r->left = lt;
		r->right = toBST(h, m+1, up);
		return r;		
	}

抱歉!评论已关闭.