Python教程

leetcode刷题_PYTHON(10):链表(10)有序链表转换二叉搜索树

本文主要是介绍leetcode刷题_PYTHON(10):链表(10)有序链表转换二叉搜索树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

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

示例:

 

 

其实蛮简单的,就是找链表中间节点作为根节点,然后再找中点两边的子链表的中点,一直递归下去直到子链表为空

特例处理:如果head为空返回空,如果head.next为空返回值为head.val的树节点
利用快慢指针找链表中间节点(slow每次走一步,fast每次走两步,循环停止时slow指向中间节点)
同时记录一下slow的前一个节点pre,这是为后面的断开操作做准备
创建树的根节点,把slow的值赋给它,并断开链表中间节点和左边子链表的连接
递归链表中间节点左右两边的子链表,找子链表的中间节点,再找子链表的子链表的中间节点,如此循环往复,直到符合特例处理的条件递归返回

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        //1. 特例处理
        if (head == null){
            return null;
        }else if(head.next == null){
            return new TreeNode(head.val);
        }
        //2. 利用快慢指针找链表中间节点
        ListNode slow = head, fast = head;
        ListNode pre = null;
        while( fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //3. 创建树的根节点,并断开相应连接
        TreeNode root = new TreeNode(slow.val);
        pre.next = null;

        //4. 递归链表中间节点左右两边的子链表
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
}

作者:edelweisskoko
链接:https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/109-you-xu-lian-biao-zhuan-huan-er-cha-s-x583/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 

这篇关于leetcode刷题_PYTHON(10):链表(10)有序链表转换二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!