目录

108.将有序数组转化为二叉搜索树

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

876.链表的中间节点

---

108.将有序数组转化为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵

平衡二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

思路：

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums,0,nums.length-1);
    }
    public TreeNode dfs(int[] nums,int begin,int end){
        if(begin > end)
            return null; 
        //将传过来的数组的中间数取出作为根节点
        int mid = begin + (end - begin) / 2;
        //创建一个根节点
        TreeNode root = new TreeNode(nums[mid]);
        //根节点确定后，递归遍历左子树和右子树
        root.left = dfs(nums,begin,mid-1);
        root.right = dfs(nums,mid+1,end); //注意：当mid+1>end时，则右子树部分结束
        return root;
    }
}

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

给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为

平衡

二叉搜索树。

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。

解法1：

与108题的思路一致，只不过这道题需将链表全部存储到结合list中

但是执行时间 1ms，只击败31.44%使用 Java 的用户

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        //将链表中的值全都存储到集合list中
        List<Integer> list = new ArrayList<>();
        while(head!= null){
            list.add(head.val); //list添加链表中的元素记得加上.val
            head = head.next;
        }
        return dfs(list,0,list.size()-1); //求list集合大小->list.size()
    }
     public TreeNode dfs(List<Integer> list,int begin,int end){
        if(begin > end)
            return null;
        int mid = begin + (end - begin)/2;
        TreeNode root = new TreeNode(list.get(mid));//list获取元素的方法 -> list.get(下标)
        root.left = dfs(list,begin,mid-1);
        root.right = dfs(list,mid+1,end);
        return root;
     }
}

了解下解法二：

0ms

击败100.00%使用 Java 的用户

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        //如果head值为空，则直接返回null
        if(head == null)
            return null;
        //如果head.next的值为空，则直接一个新节点并返回
        else if(head.next == null)
            return new TreeNode(head.val); 
        //创建三个节点
        ListNode fast = head,slow = head,pre = slow;
        //寻找中间节点
        while(fast != null &&fast.next != null){
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        //构建根节点
        TreeNode root = new TreeNode(slow.val);
        root.right = sortedListToBST(slow.next);
        slow.next = null;
        pre.next = null;
        root.left = sortedListToBST(head);
        return root;
    }
}

876.链表的中间节点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

 思路：与109题思路一致，只是不用构建右子树和左子树，直接返回该节点即可。

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head,slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}