108.将有序数组转换为二叉搜索树
#树 2024-11-14 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* build(vector<int>& nums, int start, int end) {
        if(start > end) return nullptr;
        int index = left + ((right - left) / 2);
        TreeNode* root = new TreeNode(nums[index]);
        root->left = build(nums, start, index - 1);
        root->right = build(nums, index + 1, end);
        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums,0,nums.size() - 1);
    }
};

数组构造二叉树，构成平衡树是自然而然的事情，因为大家默认都是从数组中间位置取值作为节点元素，一般不会随机取。所以想构成不平衡的二叉树是自找麻烦。

具体来说，选择中间元素作为根节点的好处有：

  • 平衡子树的大小：中间元素把数组分成两个大致相等的部分，确保树的左右子树的节点数量相差不大，避免出现一边深而另一边浅的情况。
  • 递归构建平衡性：在递归构建树时，每次选择的中间元素作为根节点，这样每次递归的树都保持平衡。这样一来，最终构建出来的树也是平衡的。

还有，切记越界检查，即if(start > end) return nullptr;