当前位置: 首页 > article >正文

C++算法练习-day49——108.将有序数组转换为二叉搜索树

题目来源:. - 力扣(LeetCode)

题目思路分析

题目要求将一个有序数组转换为一棵平衡二叉搜索树(BST)。平衡二叉搜索树的定义是:一个二叉搜索树,其中每个节点的两个子树的高度差不会超过1。

解题思路如下:

  1. 递归构建:使用递归的方法,从数组的中间元素开始构建树。选择中间元素作为当前子树的根节点,可以确保左右子树的大小尽量平衡。
  2. 分治策略:将数组分成左右两部分,左半部分用于构建当前节点的左子树,右半部分用于构建当前节点的右子树。
  3. 终止条件:递归的终止条件是数组的左右索引相遇或交错,此时应返回nullptr,表示该部分没有节点需要构建。

代码:

#include <vector>  
  
using namespace std;  
  
// 二叉树节点定义  
struct TreeNode {  
    int val;  
    TreeNode *left;  
    TreeNode *right;  
    TreeNode() : val(0), left(nullptr), right(nullptr) {}  
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}  
};  
  
class Solution {  
public:  
    // 递归函数,将数组nums中索引left到right的部分构建为BST  
    TreeNode* ArrayToBST(vector<int>& nums, int left, int right) {  
        // 终止条件:如果left大于right,说明当前部分没有节点  
        if (left > right) {  
            return nullptr;  
        }  
          
        // 计算中间索引  
        int mid = (left + right) / 2;  
          
        // 创建当前子树的根节点  
        TreeNode* node = new TreeNode(nums[mid]);  
          
        // 递归构建左子树  
        node->left = ArrayToBST(nums, left, mid - 1);  
          
        // 递归构建右子树  
        node->right = ArrayToBST(nums, mid + 1, right);  
          
        // 返回当前子树的根节点  
        return node;  
    }  
      
    // 主函数,调用递归函数构建整棵BST  
    TreeNode* sortedArrayToBST(vector<int>& nums) {  
        // 从数组的第一个元素到最后一个元素构建BST  
        TreeNode* root = ArrayToBST(nums, 0, nums.size() - 1);  
        return root;  
    }  
};

知识点摘要

  1. 二叉搜索树(BST):一种特殊的二叉树,其中每个节点的值都大于其左子树所有节点的值,且小于其右子树所有节点的值。
  2. 平衡二叉搜索树:每个节点的两个子树的高度差不会超过1的BST。
  3. 递归:一种解决问题的方法,通过函数调用自身来解决子问题,最终将子问题的解合并得到原问题的解。
  4. 分治策略:将一个大问题分成若干个小问题分别解决,然后将子问题的解合并得到原问题的解。

通过将有序数组的中间元素作为当前子树的根节点,并递归构建左右子树,可以有效地将有序数组转换为平衡二叉搜索树。这种方法利用了分治策略,将大问题分解为小问题,从而简化了问题的复杂度。递归的使用使得代码更加简洁和易于理解。此外,这种方法的时间复杂度为O(n),空间复杂度为O(log n)(由于递归调用栈的深度),是构建平衡二叉搜索树的一种高效方法。


http://www.kler.cn/a/416077.html

相关文章:

  • 深度学习——激活函数
  • Jmeter进阶篇(29)AI+性能测试领域场景落地
  • git merge :开发分支与主分支的交互
  • 数组和链表OJ题
  • 网络原理(一)—— http
  • qt QProxyStyle详解
  • 【人工智能基础】计算机视觉
  • ElementUI:el-drawer实现在父组件区域内打开抽屉组件非全屏
  • git如何创建一次没有修改的commit
  • windows C#-取消任务列表(下)
  • python画图plt.close()一直闪烁
  • webpack5提升打包构建速度(四)
  • 详解 YOLOv5 模型运行参数含义以及设置及在 PyCharm 中的配置方法
  • uniapp首页样式,实现菜单导航结构
  • 【LeetCode热题100】优先级队列
  • 微软要求 Windows Insider 用户试用备受争议的召回功能
  • 显卡驱动更新无法更新怎么办 显卡驱动无法更新原因及解决
  • Java知识及热点面试题总结(一)
  • 嵌入式 FPGA开发
  • GAMIT 单北斗sV antenna offsets for SVN c232 not found in antmod.dat
  • 华为CloudEngine S16700 V600R023C00 VXLAN概念
  • Flink CDC 锁表原理详解
  • Docker使用教程
  • go的math/rand随机数生成器
  • 蓝桥杯——递归
  • 技术总结(四十一)