leetcode 108 109

阳光穿透心脏的1/2处 2023-06-17 13:58 14阅读 0赞

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

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

示例:

给定有序数组: \[-10,-3,0,5,9\],

一个可能的答案是：\[0,-3,9,-10,null,5\]，它可以表示下面这个高度平衡二叉搜索树：

0
     / \

\-3 9  
/ /  
\-10 5  
思路: 分治法，借鉴快排

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode sortedArrayToBST(int[] nums) {
        
            
            if (nums.length == 0)
                return null;
            if (nums.length == 1)
                return new TreeNode(nums[0]);
            
            int mid = (0+nums.length)/2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = sortedArrayToBST(Arrays.copyOfRange(nums,0,mid));
            root.right = sortedArrayToBST(Arrays.copyOfRange(nums,mid+1,nums.length));
            return root;
        }
    }

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

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。  
思路： 快慢指针找到中间值，同时还必须找到中间值前一个指针，  
并使其断开。再分别递归。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode sortedListToBST(ListNode head) {
        
            
            if (head == null)return null;
            else if (head.next == null)return new TreeNode(head.val);
    
            // 找中点
            ListNode pre = head;
            ListNode find = head.next.next;
            ListNode slow = head.next;
    
            while (find != null &&find.next != null) {
        
                pre = pre.next;
                slow = slow.next;
                find  = find.next.next;
            }
            // slow 
            pre.next = null;
          
            TreeNode root = new TreeNode(slow.val);
            root.left = sortedListToBST(head);
            root.right = sortedListToBST(slow.next);
            return root;
        }
    }