递归_leetcode.109.有序链表转换二叉搜索树

发表于 | 分类于 ， | 热度: ℃
字数统计: 2.4k | 阅读时长 ≈ 10

🌸题目

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

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

示例:

1
2
3
4
5
6
7
8
9
给定的有序链表： [-10, -3, 0, 5, 9],

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

      0
     / \
   -3   9
   /   /
 -10  5

🌸分析

将给定的有序链表转换为二叉搜索树的第一步是确定根节点。由于我们需要构造
出平衡的二叉树，因此比较直观的想法是让根节点左子树中的节点个数与右子树
中的节点个数尽可能接近。这样一来，左右子树的高度也会非常接近,可以达到
度差绝对值不超过1的题目要求。

如何找出这样的一个根节点呢?我们可以找出链表元素的中位数作为根节点的
值。

这对于中位数的定义为:如果链表中的元素个数为奇数,那么唯一的中间
值为中位数;如果元素个数为偶数,那么唯二的中间值都可以作为中位数,
而不是常规定义中二者的平均值。

根据中位数的性质，链表中小于中位数的元素个数与大于中位数的元素个数要么
相等,要么相差1.此时，小于中位数的元素组成了左子树,大于中位数的元素组成了右子树，它们分别对应着有序链表中连续的一-段。在这之后，我们使用分治的思想，继续递归地对左右子树进行构造，找出对应的中位数作为根节点，以此类推。

可以证明，这样的构造方法得到的二叉搜索树是平衡的,详见文末的「正确性证
明」部分。

🌸解法一：分治

具体地，设当前链表的左端点为left,右端点right,包含关系为「左闭右开」，
即left包含在链表中而right不包含在链表中。我们希望快速地找出链表的中位
数节点mid.

为什么要设定[闭右刑的关系?于题目中给定的链表为向链表，访问后继元素十分容易,但无法直接访问前驱元素。因此在找出链表的中位数节点mid之后，如果设定「左闭右开」的关系，我们就可以直接用(left, mid)以吸(mid. next, right) 来表在子树对应的列表了。初初始的列表也可以用(head, null)方便地进行表示，中null表示空节点。

找出链表中位数节点的方法多种多样，中较为简单的一种是「快慢指针法」。
初始时，快指针fast和慢指针slow均指向链表的左端点left。我们将快指针
fast向右移动两次的同时，将慢指针slow向右移动一次，直到快指针到达边界.
(即快指针到达右端点或快指针的下一个节点是右端点)。此时，慢指针对应的
元愫就是中位数。

在找出了中位数节点之后,我们将其作为当前根节点的元素，并递归地构造其左
侧部分的链表对应的左子树，以及右侧部分的链表对应的右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public TreeNode sortedListToBST(ListNode head) {
    return buildTree(head, null);
}

public TreeNode buildTree(ListNode left, ListNode right) {
    if (left == right) {
        return null;
    }
    ListNode mid = getMedian(left, right);
    TreeNode root = new TreeNode(mid.val);
    root.left = buildTree(left, mid);
    root.right = buildTree(mid.next, right);
    return root;
}

public ListNode getMedian(ListNode left, ListNode right) {
    ListNode fast = left;
    ListNode slow = left;
    while (fast != right && fast.next != right) {
        fast = fast.next;
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# python    
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        def getMedian(left: ListNode, right: ListNode) -> ListNode:
            fast = slow = left
            while fast != right and fast.next != right:
                fast = fast.next.next
                slow = slow.next
            return slow
        
        def buildTree(left: ListNode, right: ListNode) -> TreeNode:
            if left == right:
                return None
            mid = getMedian(left, right)
            root = TreeNode(mid.val)
            root.left = buildTree(left, mid)
            root.right = buildTree(mid.next, right)
            return root
        
        return buildTree(head, None)

写法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public TreeNode sortedListToBST(ListNode head) {
    //边界条件的判断
    if (head == null)
        return null;
    if (head.next == null)
        return new TreeNode(head.val);
    //这里通过快慢指针找到链表的中间结点slow，pre就是中间
    //结点slow的前一个结点
    ListNode slow = head, fast = head, pre = null;
    while (fast != null && fast.next != null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    //链表断开为两部分，一部分是node的左子节点，一部分是node
    //的右子节点
    pre.next = null;
    //node就是当前节点
    TreeNode node = new TreeNode(slow.val);
    //从head节点到pre节点是node左子树的节点
    node.left = sortedListToBST(head);
    //从slow.next到链表的末尾是node的右子树的结点
    node.right = sortedListToBST(slow.next);
    return node;
}

或者

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public TreeNode sortedListToBST(ListNode head) {
    List<Integer> list = new ArrayList<>();
    //把链表节点值全部提取到list中
    while (head != null) {
        list.add(head.val);
        head = head.next;
    }
    return sortedListToBSTHelper(list, 0, list.size() - 1);

}

TreeNode sortedListToBSTHelper(List<Integer> list, int left, int right) {
    if (left > right)
        return null;
    //把list中数据分为两部分
    int mid = left + (right - left) / 2;
    TreeNode root = new TreeNode(list.get(mid));
    root.left = sortedListToBSTHelper(list, left, mid - 1);
    root.right = sortedListToBSTHelper(list, mid + 1, right);
    return root;
}

🌸解法二： 分治+中序遍历优化

方法一的时间复杂度的瓶颈在于寻找中位数节点。由于构造出的二叉搜索树的中序遍历结果就是链表本身,因此我们可以将分治和中序遍历结合起来，减少时间复杂度。

具体地，设当前链表的左端点编号为left, 右端点编号为right, 包含关系为「双闭]，即left和right均包含在链表中。链表节点的编号为[0,n)。中序遍历的顺序是[左子树-根节点-右子树」，那么在分治的过程中, 我们不用急着找出链表的中位数节点，而是使用一个占位节点,等到中序遍历到该节点时,再填充它的值。

我们可以通过计算编号范围来进行中序遍历:

  • 中位数节点对应的编号为mid= (left+ right + 1)/2;

    根据方法一 中对于中位数的定义,编号为(left + right)/2 的节点同样也可以是中位数节点。

  • 左右子树对应的编号范围分别为[left, mid - 1]和[mid+ 1, right]。

如果left > right, 那么遍历到的位置对应着一个空节点， 否则对应着二叉 搜索树中的一个节点。
这样一来我们其实已经知道了这棵二叉搜索树的结构,组题目给定了它的中序遍历结果,那么我们只要对其进行中序遍历，就可以还原出整棵二叉 搜索树了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
   ListNode globalNode;
   public TreeNode sortedListToBST2(ListNode head) {
   	globalNode = head;
   	int length = getLength(head);
   	return buildTree(0, length - 1);
   }
private TreeNode buildTree(int left, int right) {
	// TODO Auto-generated method stub
	if(left > right) {
		return null;
	}
	int mid = (right + left + 1) / 2;
	TreeNode root = new TreeNode();
	root.left = buildTree(left, mid - 1);
	root.val = globalNode.val;
	globalNode = globalNode.next;
	root.right = buildTree(mid + 1, right);
	return root;
}
private int getLength(ListNode head) {
	// TODO Auto-generated method stub
	int ret = 0;
	while(head != null) {
		++ret;
		head = head.next;
	}
	return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def sortedListToBST(self, head: ListNode) -> TreeNode:
    def getLength(head: ListNode) -> int:
        ret = 0
        while head:
            ret += 1
            head = head.next
        return ret
    
    def buildTree(left: int, right: int) -> TreeNode:
        if left > right:
            return None
        mid = (left + right + 1) // 2
        root = TreeNode()
        root.left = buildTree(left, mid - 1)
        nonlocal head
        root.val = head.val
        head = head.next
        root.right = buildTree(mid + 1, right)
        return root
    
    length = getLength(head)
    return buildTree(0, length - 1)

🌸正确性证明

我们需要证明的是:对于任意的有序链表，用「前言」部分的构造方法得到的二叉搜索树一定是平衡的。显然,如果二叉搜索树的左右子树都是平衡的，并且它们的高度差不超过1,那么该二叉搜索树就是平衡的。

我们使用数学归纳法,设链表的长度为n,对应的二叉搜索树的高度为H(n):

这里规定只包含根节点的二叉搜索树的高度为 1.

  • 当n= 1,2时，对应的二叉搜索树都是平衡的，并且H(1)= 1, H(2)= 2;
  • 当n=3时,对应的二叉搜索树包含一 个根节点和左右子树各一 个节点，它是平衡的,并且H(3)= 2;
  • 假设当n< $$n_0$$时，对应的二叉搜索树是平衡的，并且对于任意的1≤n<$$n_0$$-1,都有H(n+ 1) - H(n)≤1,那么当n= $$n_0$$时:
    • 如果n为奇数,设n= 2k+3,那么二叉搜索树的左右子树的大小均为k+ 1,高度相等，因此二叉搜索树平衡的，組有H(n)= H(k+ 1)+1.而n-1=2k+ 2,对应的二叉搜索树的左右子树的大小为k和k+1,即H(n-1)= H(k+ 1)+1,因此H(n)= H(n- 1);
    • 如果n为偶数，设n=2k+ 2,那么二叉搜 索树的左右子树的大小为k和k+ 1,根据假设,度差H(k+ 1)- H(k)≤1,因此二叉搜索树是平衡的，并且有H(n)= H(k+1)+ 1。而n-1= 2k+ 1
    • 对应的二叉搜索树的左右子树的大小均为k,即H(n- 1)= H(k),因此H(n)- H(n- 1)=H(k + 1)- H(k)≤1。

这样我们就证明了任意长度的链表对应的二叉搜索树是平衡的。

题解出自@LeetCode-Solution

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！

-------------本文结束感谢您的阅读-------------
云澈 wechat
扫一扫，用手机访问哦
坚持原创技术分享，您的支持将鼓励我继续创作！
0%