[LeetCode] 109. 有序链表转换二叉搜索树

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

题目描述:

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

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

示例:

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

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

      0

     / \

   -3   9

   /   /

 -10  5

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路:

与上一题108. 将有序数组转换为二叉搜索树,还是找中点

但是这个是链表找中点,所以我们用快慢指针!

代码:

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def sortedListToBST(self, head: ListNode) -> TreeNode:

        def findmid(head, tail):

            slow = head

            fast = head

            while fast != tail and fast.next!= tail :

                slow = slow.next

                fast = fast.next.next

            return slow

        def helper(head, tail):

            if  head == tail: return

            node = findmid(head, tail)

            root = TreeNode(node.val)

            root.left = helper(head, node)

            root.right = helper(node.next, tail)

            return root

        return helper(head, None)

java

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

class Solution {

   public TreeNode sortedListToBST(ListNode head) {

        if (head == null) return null;

        return helper(head, null);

    }

    private TreeNode helper(ListNode head, ListNode tail) {

        if (head == tail) return null;

        // mid

        ListNode slow = head;

        ListNode fast = head;

        while (fast != tail && fast.next != tail) {

            slow = slow.next;

            fast = fast.next.next;

        }

        TreeNode root = new TreeNode(slow.val);

        root.left = helper(head, slow);

        root.right = helper(slow.next, tail);

        return root;

    }

}

巴特西

[LeetCode] 109. 有序链表转换二叉搜索树

题目描述:

示例:

思路:

代码:

最新文章

热门文章