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

秒速五厘米 2021-09-28 11:40 216阅读 0赞

package LeetCode;
    
    
    import java.util.ArrayList;
    import java.util.List;
    
    /*
    给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
    本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
    示例:
    给定的有序链表： [-10, -3, 0, 5, 9],
    一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
          0
         / \
       -3   9
       /   /
     -10  5
     */
    public class SortedListToBST {
        public TreeNode sortedListToBST(ListNode head) {
            List<Integer> listNode = new ArrayList<>();
            ListNode node = head;
            while (node != null) {
                listNode.add(node.val);
                node = node.next;
            }
            int left = 0;
            int right = listNode.size() - 1;
            return build(left, right, listNode);
        }
    
        public TreeNode build(int left, int right, List<Integer> listNode) {
            if (left > right) return null;
            int mid = (left + right) / 2;
            TreeNode treenode = new TreeNode(listNode.get(mid));
            treenode.left = build(left, mid - 1, listNode);
            treenode.right = build(mid + 1, right, listNode);
            return treenode;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，216人围观）

还没有评论，来说两句吧...

相关阅读

相关 ( “树” 之 BST) 109. 有序链表转换二叉搜索树 ——【Leetcode每日一题】

> 二叉查找树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点。 > 二叉查找树中序遍历有序。 109. 有序链表转换二叉搜索树给定一个单链表的头

朱雀/ 2024年03月23日 16:14/ 0 赞/ 82 阅读

相关 leetcode109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。示例:

古城微笑少年丶/ 2023年06月29日 06:58/ 0 赞/ 17 阅读

相关 109. 有序链表转换二叉搜索树（JS实现）

1 题目 > 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。 > 本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝

逃离我推掉我的手/ 2023年02月21日 09:13/ 0 赞/ 22 阅读

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

题目来源 [109. 有序链表转换二叉搜索树][109.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdG

系统管理员/ 2023年02月20日 12:16/ 0 赞/ 10 阅读

相关 C语言重构【109】有序链表转换二叉搜索树

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

谁借莪１个温暖的怀抱￠/ 2022年12月21日 10:50/ 0 赞/ 144 阅读

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

1. 将有序数组转换为二叉搜索树 2. 有序链表转换二叉搜索树题目说明给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。本题中，一个高度平衡

傷城~/ 2022年12月04日 14:58/ 0 赞/ 130 阅读

相关【LeetCode 109】有序链表转换二叉搜索树

题目描述给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过

蔚落/ 2022年11月29日 03:10/ 0 赞/ 155 阅读

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

忘是亡心i/ 2022年11月05日 08:48/ 0 赞/ 118 阅读

相关 LeetCode【109.有序链表转换二叉搜索树】

题目描述 > 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。 > 本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对

矫情吗；*/ 2022年05月06日 04:26/ 0 赞/ 154 阅读

相关 109. 有序链表转换二叉搜索树(java)

package LeetCode; import java.util.ArrayList; import java.util.Lis

秒速五厘米/ 2021年09月28日 11:40/ 0 赞/ 217 阅读