【Leetcode】109.有序链表转换二叉搜索树

题目

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

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

示例:

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

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

      0
     / \
   -3   9
   /   /
 -10  5

题解

这道题和上一道类似,改动是把数组改成了链表。 链表求中间节点的经典方法是快慢指针,慢指针每次走一步,快指针每次都走两步,这样快指针走到链表结尾的时候,慢指针就指向中间节点。 这样就可以把问题转化为递归的子问题进行求解。

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        return helper(head, null);
    }

    public TreeNode helper(ListNode head, ListNode tail) {
        if (head == null || head == tail) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != tail && fast.next.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }

        TreeNode current = new TreeNode(slow.val);
        current.left = helper(head, slow);
        current.right = helper(slow.next, tail);
        return current;
    } 
}

这道题目还有一个比较巧妙的办法是利用BST中序遍历是升序的性质,去求解,具体看代码注释。

class Solution {
    private ListNode node;

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }

        int size = 0;
        ListNode runner = head;
        node = head;

        while (runner != null) {
            runner = runner.next;
            size++;
        }
        // 先计算有几个节点
        return inorderHelper(0, size - 1);
    }

    public TreeNode inorderHelper(int start, int end) {
        if (start > end) {
            return null;
        }
        // 划分左右子树
        int mid = start + (end - start) / 2;
        TreeNode left = inorderHelper(start, mid - 1);
        // 中序遍历
        TreeNode treenode = new TreeNode(node.val);
        treenode.left = left;
        node = node.next;

        TreeNode right = inorderHelper(mid + 1, end);
        treenode.right = right;

        return treenode;
    }
}

最关键的一个步骤是node = node.next 这步的意思是基于: 在BST中任意子树,它的中序遍历的结果如果存在一个链表中,一定是一个升序的,可以一一对应上,所以中序遍历完(这里是构建完)一个节点链表+1。

原文发布于微信公众号 - Leetcode名企之路(DailyLeetCode)

原文发表时间:2019-03-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券