LeetCode109----链表转为二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0

     / \

   -3   9

   /   /

 -10  5

平衡二叉查找树：简称平衡二叉树。由前苏联的数学家Adelse-Velskil和Landis在1962年提出的高度平衡的二叉树，根据科学家的英文名也称为AVL树。它具有如下几个性质：

可以是空树。
假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1

　　平衡之意，如天平，即两边的分量大约相同。如定义，假如一棵树的左右子树的高度之差超过1，如左子树的树高为2，右子树的树高为0，子树树高差的绝对值为2就打破了这个平衡。如依次插入1，2，3三个结点（如下图）后，根结点的右子树树高减去左子树树高为2，树就失去了平衡。

解题思路：

   因为题目要求生成后的二叉搜索树是要平衡的，所以我们在链表中，就以链表的中间节点作为根节点，两边的元素作为根节点的左右子树

以上面的链表为例，我们选取0作为树的根节点，然后我们继续递归，找到中间节点两边的各自的中间节点，把这两个节点作为0的左右子树。

  （1）我们可以定义两个指针，分别为fast和low，代表快慢指针，一个走两步，一个走一步，这样我们下来，low节点指向的就是中间节点0。
  （2）以-10 到-3，还是通过快慢指针，找到中间节点，5到9，通过快慢指针找到中间节点，如果还有元素，继续找中间节点。。。。
这里我们之所以不采用数组的方式，是因为我们用数组的话，会产生额外的空间复杂度O(N)，尽管解题思路还是很上面的一样，但是我们还是不这么做。

代码如下：

public class LeetCode109 {

	public static class ListNode {

		int val;

		ListNode next;

		ListNode(int x) {

			val = x;

		}

	}

	public static class TreeNode {

		int val;

		TreeNode left;

		TreeNode right;

		TreeNode(int x) {

			val = x;

		}

	}

	public TreeNode sortedListToBST(ListNode head) {

		if (head == null) {

			return null;

		}

		if (head.next == null) {

			return new TreeNode(head.val);

		}

		TreeNode root = getRoot(head);

		return root;

	}

	private TreeNode getRoot(ListNode head) {

		if (head == null) {

			return null;

		}

		if (head.next == null) {

			return new TreeNode(head.val);

		}

		ListNode fast = head;

		ListNode low = head;

		ListNode prev = head;

		boolean flag = false;

		while (fast != null) {

			if (fast.next == null || fast.next.next == null) {

				break;

			}

			prev = low;

			fast = fast.next.next;

			low = low.next;

			flag = true;

		}

		ListNode next = low.next;

		prev.next = null;

		TreeNode root = new TreeNode(low.val);

		if (prev != head || flag) {

			root.left = getRoot(head);

		}

		root.right = getRoot(next);

		return root;

	}

}

巴特西

LeetCode109----链表转为二叉搜索树

最新文章

热门文章