【LeetCode】109. 有序链表转换二叉搜索树 - 快慢指针对链表求中间点

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

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

给定的有序链表: [-10, -3, 0, 5, 9],
一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:

      0
     / \
   -3   9
   /   /
 -10  5

思路 1:链表遍历完,放入数组,再对数组进行二分递归构造树,这里仅提供思路
思路 2:快慢指针求链表中间节点(可以画图进行演示,很好理解),在对左右子链表递归构造二叉排序树。

TreeNode* sortedListToBST(ListNode* head) {
    if(!head)
        return nullptr;
    // 下面是快慢指针求中间节点的过程
    ListNode* slow = head;
    ListNode* fast = head;
    ListNode* pre = nullptr; // 用于对链表进行分段
    
    while(fast && fast->next){
        pre = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    // 这时slow即为中间节点,可以自己画图演示
    
    TreeNode* root = new TreeNode(slow->val);
    
    if(pre){// 确保发生了分组,最后两个节点会出错
        //断链操作 |head...slow-1(pre) | slow | slow->next....nullptr|  
        pre = nullptr;
        root->left = sortedListToBST(head);
        root->right= sortedListToBST(slow->next);
    }
    return root;
}

本文链接:https://ariser.cn/index.php/archives/368/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!