순서 배열을 이진 검색 트리로 변환하는 방법

이 기사의 내용은 순서 배열을 이진 검색 트리로 변환하는 방법에 대한 것입니다. 특정 참조 값이 있으므로 도움이 될 수 있습니다.

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

재귀를 사용할 때마다 배열의 중간 값을 현재 노드로 간주하고 왼쪽 값을 반복하여 왼쪽 자식을 생성하고 오른쪽 값을 하나는 재귀입니다. 아래로 내려가서 올바른 자식을 생성하세요.

위 내용은 순서 배열을 이진 검색 트리로 변환하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!