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

文章目录

【LeetCode】109. 有序链表转换二叉搜索树题目描述解题思路代码总结

题目描述

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

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

解题思路

很多人一来看到平衡二叉树的要求，第一反应应该还是使用旋转的思路。 但二叉树类题其实在解决时一般依靠递归解。 此题类似于二叉堆的排序，由于元素是线性有序的，因此只要确定中间节点再递归建树即可。同时，中间元素的确定使用双指针，快指针一次走两步，满指针一次一步。当快指针到底时，慢指针即为中间节点。

代码

（Python解法）

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sortedListToBST(self, head: ListNode) -> TreeNode: if head is None: return None if(head.next is None): val=head.val new = TreeNode(val) return new # 双指针法 pre=head p=pre.next q=p.next while q is not None and q.next is not None: pre=pre.next # 慢指针一次走一步 p=pre.next # 快指针一次走两步 q=q.next.next pre.next=None # 递归建树 root=TreeNode(p.val) root.left=self.sortedListToBST(head) root.right=self.sortedListToBST(p.next) return root

总结

有序链表一般可考虑双指针解法