159273b779096424b473029f487a4208
(难度Medium) Problem 109. Convert Sorted List to Binary Search Tree(链表转BST)

Convert Sorted List to Binary Search Tree

Difficulty

Medium

Description

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

题意

和上一题几乎一模一样,唯一的区别是上一题当中给定的是一个vector,而这题改成了链表。

深深地感受到了题目的恶意,比较容易想到我们完全可以手动把链表转化成vector完成转换的操作。我们并没有学到什么新的内容,也没有什么特别的技巧或者是用法,不管怎么看都有点鸡肋。

但是如果我们不把链表转成vector有没有办法解决呢?有没有办法直接递归生成BST呢?

因为对于一棵BST而言,我们已经知道如果我们中序遍历它,那么得到的结果就应该是升序的。也就是说如果我们要根据升序的序列生成BST,那么我们应该倒过来生成。

top Created with Sketch.