【LeetCode】T108 有序数组转为二叉搜索树

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

思路:遇到有序数组,一般首先会想到二分法。中间值做根节点,递归构建左子树和右子树。二分递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* helper(vector<int>& nums, int low, int high){
        if(low > high)
            return nullptr;
        
        int mid = low + (high-low)/2;
        TreeNode* root = new TreeNode(nums[mid]); // 中间值做根节点
        
        root->left = helper(nums, low, mid-1);
        root->right = helper(nums, mid+1, high);
        return root;
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.empty())
            return nullptr;
        
        return helper(nums, 0, nums.size()-1);
    }
};

本文链接:https://ariser.cn/index.php/archives/353/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!