Comment convertir un tableau ordonné en arbre de recherche binaire

Le contenu de cet article explique comment convertir un tableau ordonné en un arbre de recherche binaire. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Titre

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

Idée

Utiliser la récursivité, à chaque fois La valeur médiane dans le tableau est considéré comme le nœud actuel, puis celui de gauche est récuré pour générer l'enfant de gauche, et celui de droite est récuré pour générer l'enfant de droite.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!