HHot 100C++ 图解

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

简单 二叉树 3 帧动画 在力扣上做

一句话套路取中点做根,左右两半递归

题目描述

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

 

示例 1:

输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:

示例 2:

输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

 

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 按 严格递增 顺序排列

思路

时间O(n)
空间O(log n)

思路

取中间元素做根,左右两半递归建子树 —— 天然高度平衡(AVL 式建法)。

说明

答案不唯一(偶数长度时选中位数左/右都可以),所以测试断言的是「性质」而不是「形状」:中序遍历等于原数组 + 判定为合法 BST。

为了这个断言,本题的 TEST 写到了 Q98 后面(需要复用它的 isValidBST)。

图解

-10 0 3 5 9
有序数组 [-10,-3,0,5,9]:取中点为根(0),左半[-10,-3]做左子树、右半[5,9]做右子树。因为有序,中点即「大小居中」。

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/08_binary_tree.cpp16 行
namespace lc0108 {
class Solution {
 public:
  TreeNode* sortedArrayToBST(vector<int>& nums) { return build(nums, 0, (int)nums.size() - 1); }

 private:
  static TreeNode* build(const vector<int>& a, int l, int r) {
    if (l > r) return nullptr;
    int mid = l + (r - l) / 2;  // 防溢出写法,面试常问
    TreeNode* root = new TreeNode(a[mid]);
    root->left = build(a, l, mid - 1);
    root->right = build(a, mid + 1, r);
    return root;
  }
};
}

↑↓ 选择↵ 打开/ 随时唤起