How to convert ordered array to binary search tree

The content of this article is about how to convert an ordered array into a binary search tree. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Question

/**
 * 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* sortedArrayToBST(vector<int>& nums) {
        if(nums.size()==0)
            return nullptr;
        if(nums.size()==1)
            return new TreeNode(nums[0]);
        int middle=nums.size()/2;
        
        auto root=new TreeNode(nums[middle]);
        vector<int> left(nums.begin(),nums.begin()+middle);
        vector<int> right(nums.begin()+middle+1,nums.end());
        
        root->left=sortedArrayToBST(left);
        root->right=sortedArrayToBST(right);
        
        return root;
        
    }
    
};

Copy after login

The above is the detailed content of How to convert ordered array to binary search tree. For more information, please follow other related articles on the PHP Chinese website!