深度优先遍历 DFS
解题思路
BST 的中序遍历是升序的，等同于根据中序遍历的序列恢复二叉搜索树；
可以让 升序序列 的 中间元素 作为根节点（高度平衡），不断递归左子树和右子树；
这样得到的树就是一棵二叉搜索树；
复杂度
-
时间复杂度：
O(n)，其中 n 是数组的长度，每个数字只访问一次； -
空间复杂度：
O(logn)，其中 n 是数组的长度，空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是O(logn)；
代码实现
var sortedArrayToBST = function (nums) {
if (nums.length === 0) return null;
// 以升序数组的中间元素作为根节点 root
const mid = nums.length >> 1;
const root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(nums.slice(0, mid));
root.right = sortedArrayToBST(nums.slice(mid + 1));
return root;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 1019. 链表中的下一个更大节点
上一篇
评论
