Skip to content

Latest commit

 

History

History
53 lines (35 loc) · 1.74 KB

0109-convert-sorted-list-to-binary-search-tree.adoc

File metadata and controls

53 lines (35 loc) · 1.74 KB
Raw

109. Convert Sorted List to Binary Search Tree

{leetcode}/problems/convert-sorted-list-to-binary-search-tree/[LeetCode - 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.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:
Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

解题分析

这道题跟 108. Convert Sorted Array to Binary Search Tree 类似。可以转化成数组（或链表）进行求解。这属于空间换时间的解法。

另外一种解法，就是使用快慢指针，找到中间节点，然后再构造二叉树。

还有一种解法：利用分治+中序遍历，先逐步构建左树，然后构建根节点，最后构建右树。

参考资料

link:{sourcedir}/_0109_ConvertSortedListToBinarySearchTree.java[role=include]
link:{sourcedir}/_0109_ConvertSortedListToBinarySearchTree_2.java[role=include]
link:{sourcedir}/_0109_ConvertSortedListToBinarySearchTree_21.java[role=include]