LeetCode 109. 有序链表转换二叉搜索树

忘是亡心i 2022-11-05 08:48 84阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[官方][Link 1]

//快慢指针找中点，从中点二分建立二叉搜索树
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public TreeNode sortedListToBST(ListNode head) {
        
            return build(head, null);
        }
    
        private TreeNode build(ListNode left, ListNode right){
        
            if(left == right){
        
                return null;
            }
            ListNode mid = getMid(left, right);
            TreeNode root = new TreeNode(mid.val);
            root.left = build(left, mid);
            root.right = build(mid.next, right);
            return root;
        }
    
        private ListNode getMid(ListNode left, ListNode right){
        
            ListNode slow = left;
            ListNode fast = left;
            while(fast != right && fast.next != right){
        
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221023/1b49fa7a67e947dea2e2d7ae8d47628f.png
[Link 1]: https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-1-3/