LeetCode--108. 将有序数组转换为二叉搜索树（C++描述）

- 日理万妓 2022-09-12 04:00 135阅读 0赞

// Source : https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/  
// Date : 2021-09-20  
题目描述：  
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。  
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2w5peg5LiA55So5piv5Lmm55Sf_size_7_color_FFFFFF_t_70_g_se_x_16]  
输入：nums = \[-10,-3,0,5,9\]  
输出：\[0,-3,9,-10,null,5\]  
解释：\[0,-10,5,null,-3,null,9\] 也将被视为正确答案：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2w5peg5LiA55So5piv5Lmm55Sf_size_7_color_FFFFFF_t_70_g_se_x_16 1]

示例 2：  
![在这里插入图片描述][54c6d1cbdee3429cbe7ce1fdc70a30c9.png]

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

提示：

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

题目分析：本题可以理解为：利用数组画出一颗二叉树，二叉树的高度满足一定的要求（画出的二叉树也是利用数组进行存储），因此我们可以选择数组中间（或者中间位置的左右两侧）位置作为树根，然后根据这个位置，将数组分为高低两部分，继续选择每部分的中间（或者中间位置的左右两侧）位置作为树根…依次类推，可以看出：我们可以利用递归来进行树的建立。

结果代码：

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
        
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) {
        
            //传入数组、首元素下标、尾元素下标
            return helper(nums, 0, nums.size() - 1);
        }
        TreeNode* helper(vector<int>& nums, int left, int right) {
        
            if (left > right) {
        
                return nullptr;
            }
    
            // 总是选择中间位置右边的数字作为根节点
            int mid = (left + right + 1) / 2;
    
            //将该位置的元素做为树根
            TreeNode* root = new TreeNode(nums[mid]);
    
            //对于左右子树，只需递归调用该函数即可
            root->left = helper(nums, left, mid - 1);
            root->right = helper(nums, mid + 1, right);
            
            //将创建好的root数组返回
            return root;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2w5peg5LiA55So5piv5Lmm55Sf_size_7_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/2dd603055dbd459f81b75331a5b57e2f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2w5peg5LiA55So5piv5Lmm55Sf_size_7_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/0bd69ecaaead4a4287fba9bd91fc4f03.png
[54c6d1cbdee3429cbe7ce1fdc70a30c9.png]: /images/20220828/101af9b47c4b4abbae488ef485ec3476.png