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

##Code

/**
 * 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;
        
    }
    
};

Idea

Use a recursive method to add data to the array each time The value in the middle is regarded as the current node, and then the left one is recursed to generate the left child, and the right one is recursed to generate the right child.

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!