Java版LeetCode

Appearance

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

树 二叉搜索树 链表 分治 二叉树

题目 ​

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

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

示例 1:

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

示例 2:

输入: head = []
输出: []

提示:

  • head 中的节点数在[0, 2 * 104] 范围内
  • -105 <= Node.val <= 105

题解 ​

java
public TreeNode sortedListToBST(ListNode head) {
    List<Integer> list = new ArrayList<>();
    // 链表转数组
    while (head != null) {
        list.add(head.val);
        head = head.next;
    }

    BiFunction<Integer, Integer, TreeNode> recursion = new BiFunction<Integer, Integer, TreeNode>() {
        @Override
        public TreeNode apply(Integer begin, Integer end) {
            if (begin > end) {
                return null;
            }
            // 取中间节点为根节点
            int mid = (begin + end) / 2;
            TreeNode node = new TreeNode(list.get(mid));
            // 递归生成左树
            node.left = this.apply(begin, mid - 1);
            // 递归生成右树
            node.right = this.apply(mid + 1, end);
            return node;
        }
    };

    return list.size() == 0 ? null : recursion.apply(0, list.size() - 1);
}