So konvertieren Sie ein geordnetes Array in einen binären Suchbaum

Der Inhalt dieses Artikels befasst sich mit der Konvertierung eines geordneten Arrays in einen binären Suchbaum. Ich hoffe, dass er für Freunde hilfreich ist.

Titel

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

Idee

Verwenden Sie Rekursion, um das Array jeweils zum Array hinzuzufügen time Der mittlere Wert wird als aktueller Knoten betrachtet, und dann wird der linke rekursiv verwendet, um das linke Kind zu generieren, und der rechte wird rekursiert, um das rechte Kind zu generieren.

Das obige ist der detaillierte Inhalt vonSo konvertieren Sie ein geordnetes Array in einen binären Suchbaum. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!