hot 100 108. 将有序数组转换为二叉搜索树

问题描述

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

样例输入

nums=[-10,-3,0,5,9]

样例输出

[0,-3,9,-10,null,5]

评测用例规模与约定

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 按 严格递增 顺序排列

解析

分治+递归：
找到中间结点，从中间节点拆成左右2部分。每部分构建一颗树，将其赋值给中间节点左右节点。
递归核心3个点：
1、终止条件
2、每一层做什么事情（只关心当前层！）
3、给上一层返回啥

参考程序

classSolution{public:TreeNode*dfs(vector<int>&nums,intleft,intright){if(left==right)returnnullptr;intm=left+(right-left)/2;returnnewTreeNode(nums[m],dfs(nums,left,m),dfs(nums,m+1,right));}TreeNode*sortedArrayToBST(vector<int>&nums){returndfs(nums,0,nums.size());}};

难度等级

⭐️⭐️⭐️（1~10星）

以个人刷题整理为目的，如若侵权，请联系删除~