0%

leetcode每日一题-有序链表转换二叉搜索树

Posted on In ,

有序链表转换二叉搜索树

image1

方法一：链表转换为数组

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

首先遍历链表将其存入list，方便后续处理。之后的过程就和108题一模一样了。

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
/**
12
 * Definition for a binary tree node.
13
 * public class TreeNode {
14
 *     int val;
15
 *     TreeNode left;
16
 *     TreeNode right;
17
 *     TreeNode() {}
18
 *     TreeNode(int val) { this.val = val; }
19
 *     TreeNode(int val, TreeNode left, TreeNode right) {
20
 *         this.val = val;
21
 *         this.left = left;
22
 *         this.right = right;
23
 *     }
24
 * }
25
 */
26
class Solution {
27
    List<ListNode> nodelist;
28
    public TreeNode sortedListToBST(ListNode head) {
29
        if(head == null){
30
            return null;
31
        }
32
        nodelist = new ArrayList<ListNode>();
33
        while(head != null){
34
            nodelist.add(head);
35
            head = head.next;
36
        }
37
        return buildTree(0, nodelist.size()-1);
38
    }
39
40
    public TreeNode buildTree(int start, int end){
41
        if(start > end){
42
            return null;
43
        }
44
        int mid = (start+end)/2;
45
        TreeNode node = new TreeNode(nodelist.get(mid).val);
46
        node.left = buildTree(start, mid-1);
47
        node.right = buildTree(mid+1, end);
48
        return node;
49
    }
50
}

复杂度分析：

  • 时间复杂度：$O(n)$，$n$是链表长度。
  • 空间复杂度：$O(n+logn)$，需要额外空间存储list。

方法二：快慢指针法

我们也可以利用快慢指针法去获得链表中的中位数。快指针每次移动两次，慢指针每次移动一次，当快指针指向右边界或者快指针的下一位为右边界时，那么慢指针此时就是中位数。

1
class Solution {
2
    public TreeNode sortedListToBST(ListNode head) {
3
        if(head == null){
4
            return null;
5
        }
6
        return buildTree(head, null);
7
    }
8
9
    public TreeNode buildTree(ListNode start, ListNode end){
10
        if(start == end){
11
            return null;
12
        }
13
        ListNode mid = getMedian(start, end);
14
        TreeNode node = new TreeNode(mid.val);
15
        node.left = buildTree(start, mid);
16
        node.right = buildTree(mid.next, end);
17
        return node;
18
    }
19
20
    public ListNode getMedian(ListNode left, ListNode right){
21
        ListNode fast = left;
22
        ListNode slow = left;
23
        while(fast != right && fast.next != right){
24
            fast = fast.next;
25
            fast = fast.next;
26
            slow = slow.next;
27
        }
28
        return slow;
29
    }
30
}

复杂度分析：

  • 时间复杂度：$O(nlogn)$，每次递归构造都要花$O(n)$的时间找中位数。
  • 空间复杂度：$O(logn)$。

方法三：中序遍历优化

可以发现链表的顺序就是将二叉搜索树中序遍历的顺序，那么可以在对链表进行遍历的时候，按照中序遍历的顺序即左子树-根-右子树的顺序递归构造二叉搜索树。

1
class Solution {
2
    ListNode h;
3
    public TreeNode sortedListToBST(ListNode head) {
4
        if(head == null){
5
            return null;
6
        }
7
        h = head;
8
        int length = getLength(head);
9
        return buildTree(0, length-1);
10
    }
11
12
    public TreeNode buildTree(int start, int end){
13
        if(start > end){
14
            return null;
15
        }
16
        TreeNode root = new TreeNode();
17
        int mid = (start+end)/2;
18
        root.left = buildTree(start, mid-1);
19
        root.val = h.val;
20
        h = h.next;
21
        root.right = buildTree(mid+1, end);
22
        return root;
23
    }
24
25
    public int getLength(ListNode head){
26
        int len = 0;
27
        while(head != null){
28
            head = head.next;
29
            len++;
30
        }
31
        return len;
32
    }
33
}

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(logn)$。