LeetCode 109. 有序链表转换二叉搜索树（快慢指针+递归）

Michael阿明

发布于 2020-07-13 14:30:13

4120

发布于 2020-07-13 14:30:13

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

1. 题目

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

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree

类似题目 LeetCode 108. 将有序数组转换为二叉搜索树

2. 解题

类似的方法，快慢指针找到链表中点作为树的 root
在中点前断开链表，递归进行
递归终止条件 head 为空，返回 NULL，如果只有一个节点了（head = slow），直接返回head处的值建立的 root

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(!head) return NULL;
        ListNode *slow, *slow_pre, *fast;
        slow = fast = head;
        slow_pre = NULL;
        while(fast && fast->next) 
        {
        	slow_pre = slow;
        	slow = slow->next;
        	fast = fast->next->next;
        }
        if(slow_pre)
        	slow_pre->next = NULL;//断开链表
        if(slow && slow != head)
        {
        	TreeNode *root = new TreeNode(slow->val);
        	root->left = sortedListToBST(head);
        	root->right = sortedListToBST(slow->next);
        	return root;
        }
        return new TreeNode(head->val);
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/09/17 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树