首页 > ACM题库 > LeetCode > 有序链表转化为平衡的二分查找树
2014
09-10

有序链表转化为平衡的二分查找树

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.

题目链接:https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

 

方法一

比较直观的解法是自顶向下的递归解决,先找到中间节点作为根节点,然后递归左右两部分。所有我们需要先找到中间节点,对于单链表来说,必须要遍历一边,可以使用快慢指针加快查找速度。

Java代码如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        if(head.next == null){
            return new TreeNode(head.val);
        }
        //用快慢指针找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        ListNode preSlow = null;
        while(fast.next != null && fast.next.next != null){
            preSlow = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //分别递归左右两部分
        TreeNode mid = new TreeNode(slow.val);
        if(preSlow != null){
            preSlow.next = null;
            mid.left = sortedListToBST(head);
        }
        if(slow.next != null){
            mid.right = sortedListToBST(slow.next);
        }
        return mid;
    }
}

时间复杂度为O(nlgn),由于找到中间节点需要O(n)的时间复杂度,有没有办法不找中间节点?

 方法二

上面的方法是自顶向下,我们也可以采用自底向上的递归来解决。可以在遍历的链表的同时生成树的节点。这种方法我们先需要遍历链表一次,得到链表的总长度,然后也是递归的调用下去。这个递归和上面的不同之处在于,我们需要修改head指针,因此需要传入指针的指针,C++的写法就是:ListNode *& head或 ListNode ** head

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
  if (start > end) return NULL;
  // same as (start+end)/2, avoids overflow
  int mid = start + (end - start) / 2;
  BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
  BinaryTree *parent = new BinaryTree(list->data);
  parent->left = leftChild;
  list = list->next;
  parent->right = sortedListToBST(list, mid+1, end);
  return parent;
}

BinaryTree* sortedListToBST(ListNode *head, int n) {
  return sortedListToBST(head, 0, n-1);
}

由于Java里面只能传引用(也就是一级指针),所以需要用ListNodeWrapper类包装一下。

//============================================================================
// Name        : SortedListToBST.java
// Author      : GaoTong
// Date        : 2014/9/7
// Copyright   : www.acmerblog.com
//============================================================================
public class SortedListToBST {

    public static TreeNode sortedListToBST(ListNode head) {
        int len = 0;
        ListNode tmp = head;
        while(tmp != null){
            len++;
            tmp = tmp.next;
        }
        ListNodeWrapper headWrapper = new ListNodeWrapper();
        headWrapper.node = head;
        return sortedListToBST(headWrapper, 0, len-1);
    }

    public static TreeNode sortedListToBST(ListNodeWrapper headWrapper, int start, int end){
        if(start > end) return null;
        int mid = start + (end-start)/2;
        TreeNode left = sortedListToBST(headWrapper, start, mid-1);
        TreeNode parent = new TreeNode(headWrapper.node.val);
        parent.left = left;
        headWrapper.node = headWrapper.node.next;
        parent.right = sortedListToBST(headWrapper, mid+1, end);
        return parent;
    }

    static class ListNodeWrapper {
        ListNode node;
    }

}

时间复杂度为:O(n)

参考:http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html