Skip to content

Latest commit

 

History

History

108. Convert Sorted List to Binary Search Tree

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

这道题别扭之处在于这个链表,但 LeetCode 的人性之处在于让其有序,因为排序属于另一个考点,让一道题的重心放在某一点上,更容易在短时间内考察一个程序员的基本素养。

对于有序链表来说,平衡 BST 显然是需要其中间结点来作为根节点的。

于是毫无疑问的,第一步就要知道中点在哪,要知道中点,就需要知道链表的长度


假设链表长度为 n,我们希望按照链表的顺序来构建这个平衡 BST,那么就是从左边的子树开始,到根,再到右子树。这似乎有点违背常理,因为咱们一般习惯从根节点构建二叉树。

从左子树开始,是因为最左边的子树恰好对应着链表的第一个节点。然后该子树的根,对应第二个节点,该子树的右子树或父节点,对应第三个节点,以此类推。

这个过程有点类似咱们熟知的 DFS,但又不完全是,因为 DFS 也是从根节点开始的。但我们可以模仿 DFS 的递归算法来构建咱们的解决方案。


设计一个递归结构的 sortedListToBST 很有必要:

TreeNode *sortedListToBST(ListNode **head_ref, int n) // 我们需要链表节点的引用,以及长度 n
{
    if (n<1) return NULL; // 如果长度为0或负数,肯定不考虑了
    TreeNode *left = sortedListToBST(head_ref, n/2); // 递归的去解决左子树,其最深的位置,便是最左节点,刚好对应 head。而左边的长度,恰为 n 的一半
    TreeNode *root = new TreeNode((*head_ref)->val); // 解决完左子树,接下来就是根节点,new 出根节点,并赋予 head 当前指向的值
    // 接下来显然应该是递归的解决右子树,但注意,head 指针目前仍指向根节点,我们需要先将其向后移动,同时,也应该将 root 的 left 指向上面的左子树递归结果
    root->left = left;
    *head_ref = (*head_ref)->next;
    // 然后递归的解决右子树
    root->right = sortedListToBST(head_ref, n-n/2-1); // 注意要减掉根节点的占位。
    return root;
}

问题完美解决。效率中等,这个方案貌似已经被人用烂了,但的确最直接最自然,效率也不低。不失为一种非常优美的解决方案。