【LeetCode二叉树#19】有序数组转换为二叉搜索树（构造二叉树）

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

力扣题目链接(opens new window)

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

思路

本题还是考察的构建二叉树

之前也有做过类似的题目，基本上来说，构造二叉树就是按照题目规则找根节点，然后调用递归不断构造出其左右子树即可

那么，本题的规则是什么？

题目要求我们将升序排列的有序数组，转换为一棵高度平衡二叉搜索树

因此，可以用数组的中间值为根节点来构造二叉搜索树

如果之后再来复习，肯定会想：如果中间值有两个怎么办

那现在先举个例子说明一下：

[1,2,3,4,5,6]

这里如果取中间值会有两个数，分别是3和4

实际上这不影响我们去构造一颗高度平衡二叉搜索树，因为不论选3还是4作为根节点，其左或右子树多出的一个节点也不会破坏高度的平衡

在这里，我们默认取左边的值（后面会说明原因）

确定了根节点之后，还是像之前的构建二叉树的题目，通过递归不断分割左右区间，进而构建出根节点的左右子树

代码

分析

使用递归法

1、确定递归函数的参数和返回值

不要一写参数就下意识的填根节点，这里都还没有找出根节点呢

因为要通过分割数组来构建二叉树，所以输入参数中肯定有数组nums，以及用于分割的左右区间

并且，我们需要返回的是一颗二叉树，那么返回值显然就是该树的根节点了

TreeNode* traversal(vector<int> nums, int left, int right){
    
}

2、确定终止条件

同理，不要一写终止条件就下意识的root==NULL

这里的终止条件应该与左右边界有关

即当 left > right 时应该结束

TreeNode* traversal(vector<int> nums, int left, int right){
    //确定终止条件
    if(left > right) return NULL;
    
    
}

3、确定单层处理逻辑

现在要开始取数组的中间值并分割数组

TreeNode* traversal(vector<int> nums, int left, int right){
    //确定终止条件
    if(left > right) return NULL;
    
    //确定单层处理逻辑
    //取中间值
    int mid = (right - left)/2 + left;
}

为什么这样取中间值？

因为如果直接(right + left) / 2，当right、left均为int下的最大值，会导致数据溢出

上述方法可以避免这种问题，详见

TreeNode* traversal(vector<int> nums, int left, int right){
    //确定终止条件
    if(left > right) return NULL;
    
    //确定单层处理逻辑
    //取中间值
    int mid = (right - left)/2 + left;
    //创建根节点
    TreeNode* root = new TreeNode(nums[mid]);
    //调用递归继续构建左右子树
    root->left = traversal(nums, left, mid - 1);//跳过mid
    root->right = traversal(nums, mid + 1, right);
    return root;   
}

注意，在分割数组时要跳过mid处的值

完整代码

class Solution {
public:
    //确定递归函数的参数与返回值
    TreeNode* traversal(vector<int>& nums, int left, int right){
        //确定终止条件
        if(left > right) return NULL;
        //确定单层处理逻辑
        //先找到数组里的中间值
        int mid =(right - left) / 2 + left;//防止数据溢出
        //初始化根节点
        TreeNode* root = new TreeNode(nums[mid]);
        //递归处理分割后数组的左区间和右区间
        //注意要跳过mid
        root->left = traversal(nums, left, mid - 1);
        root->right = traversal(nums, mid + 1, right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return traversal(nums, 0 , nums.size() - 1);
    }
};

构造二叉树的注意事项

1、找根节点

一般来说，没有特殊规定就找中间值作为根节点

本题中要求构建的二叉树为高度平衡的二叉搜索树，正好选中间值可以满足条件

2、根本原理

总结一下这几题构造二叉树的套路，无外乎：找根节点、递归分割数组构建左右子树

值得注意的是，在本题中，我们没有对nums本身进行操作，而是利用其下标进行的分割

而在之前做的几题里，我们分割数组时使用了**新建数组的方式