【Leetcode】108. Convert Sorted Array to Binary Search Tree（左右子树节点平衡）

迷南。 2022-02-17 04:15 124阅读 0赞

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of *every* node never differ by more than 1.

**Example:**

Given the sorted array: [-10,-3,0,5,9],
    
    One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
    
          0
         / \
       -3   9
       /   /
     -10  5

题目大意：

给出一个有序数组，我们需要计算出一颗高度平衡的BST。每个节点的左右子树上的节点数不超过1。

解题思路：

找出左右子树的中心点mid即可 mid=（r+l+1）/2

其结果答案不唯一。

/**
     * 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 {
    private:
        
        TreeNode* dfs(vector<int>& nums, int left, int right){
            if(left == right){
                TreeNode *tmp = new TreeNode(nums[left]);
                return tmp;
            }else if(left>right){
                return nullptr;
            }
            int mid = (right + left + 1)/2;
            TreeNode *root = new TreeNode(nums[mid]);
            
            root->left = dfs(nums, left, mid-1);
    
            root->right = dfs(nums, mid+1, right);
            
            return root;
            
        }
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) {
            return dfs(nums, 0, nums.size()-1);
        }
    };