leetcode108 将有序数组转换为二叉搜索树

一时失言乱红尘 2022-12-11 15:01 113阅读 0赞

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

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

示例:

给定有序数组: `[-10,-3,0,5,9]`,一个可能的答案是：`[0,-3,9,-10,null,5]`，

它可以表示下面这个高度平衡二叉搜索树：

0
         / \
       -3   9
       /   /
     -10  5

**递归解法**

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) {
            return dfs(nums, 0, nums.size() - 1);
    
        }
        TreeNode* dfs(vector<int>& nums, int l, int h)
        {
            if(l > h)
                return nullptr;
            int mid = l + (h - l) /  2;
            TreeNode* root = new TreeNode(nums[mid]);
            // 递归的构建 root 的左子树与右子树。
            root->left = dfs(nums, l, mid - 1);
            root->right = dfs(nums, mid + 1, h); 
            return root;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode_二叉搜索树_简单_108.将有序数组转换为二叉搜索树

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二

拼搏现实的明天。/ 2023年10月06日 23:01/ 0 赞/ 15 阅读

相关 leetcode108 将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。示例: 给定有

一时失言乱红尘/ 2022年12月11日 15:01/ 0 赞/ 114 阅读

相关【leetcode.108】将有序数组转换为二叉搜索树

一、题目描述将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

短命女/ 2022年12月10日 07:06/ 0 赞/ 123 阅读

相关 leetcode算法【108】将有序数组转换为二叉搜索树

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

朴灿烈づ我的快乐病毒、/ 2022年11月26日 06:58/ 0 赞/ 26 阅读

相关 108. 将有序数组转换为二叉搜索树

题目描述：给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差

小鱼儿/ 2022年11月12日 01:48/ 0 赞/ 122 阅读

相关 LeetCode--108. 将有序数组转换为二叉搜索树（C++描述）

// Source : https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

- 日理万妓/ 2022年09月12日 04:00/ 0 赞/ 118 阅读

相关 leetcode 108.将有序数组转换为二叉搜索树(python)

【前言】 python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/

超、凢脫俗/ 2022年05月19日 08:48/ 0 赞/ 138 阅读

相关 Leetcode 将有序数组转换为二叉搜索树

问题描述： ![70][] 算法思路：注意到给定的数组是已经升序排列的，显然树的根节点为数组中点，那根节点的左子树和右子树又在数组什么位置呢？假设数组中点的下标为m

谁践踏了优雅/ 2022年05月09日 10:20/ 0 赞/ 153 阅读

相关 leetcode 108. 将有序数组转换为二叉搜索树(java)

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。示例:

小咪咪/ 2022年04月15日 03:16/ 0 赞/ 170 阅读

相关 leetcode： 108. 将有序数组转换为二叉搜索树

package LeetCode; / 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一

浅浅的花香味﹌/ 2021年09月28日 10:44/ 0 赞/ 308 阅读