[LeetCode] 108, 질서 있 는 배열 을 이 진 트 리 로 변환

제목 설명
오름차 순 으로 배 열 된 질서 있 는 배열 을 고도 균형 이 잡 힌 이 진 트 리 로 변환 합 니 다.
이 문제 에서 하나의 높이 균형 이 진 트 리 는 이 진 트 리 의 각 노드 의 좌우 두 개의 나무의 높이 차 이 를 말 하 는 절대 치 는 1 을 초과 하지 않 는 다.
예시:

      : [-10,-3,0,5,9],

        ：[0,-3,9,-10,null,5]，                  ：

      0
     / \
   -3   9
   /   /
 -10  5

문제 풀이 의 사고 방향.
2 분 + 재 귀 건축 수.

밸 런 스 이 진 트 리 는 두 가 지 를 확보 해 야 합 니 다.

뿌리 노드 는 왼쪽 나무 임 의 노드 보다 크 고 오른쪽 나무 임 의 노드

보다 작다.

좌우 자 수 높이 의 차 이 는 1

을 초과 하지 않 는 다.

상기 성질 에서 실행 가능 한 귀속 조건 을 얻 을 수 있다.

매번 돌아 오 는 뿌리 노드 는 배열 중간 에 있 고 좌우 반 배열 로 각각 좌우 서브 트 리

를 재 귀적 으로 구성한다.

그러면 왼쪽 은 뿌리 보다 작고 오른쪽 은 뿌리 보다 크 며 모든 노드 의 좌우 서브 트 리 노드 의 차이 가 1 을 초과 하지 않 는 다 는 것 을 의미한다 (재 귀 된 구조 트 리 방식 이 같 기 때문에 모든 노드 가 고도 의 균형 을 만족시킨다)

주: 이 문제 의 답 은 유일한 것 이 아니 기 때문에 테스트 용례 결과 와 백 스테이지 의 답 이 다 를 때 도 꼭 틀린 것 은 아니다.
참조 코드

/**
 * 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) {
        int length = nums.size();
        if(length == 0)
            return nullptr;
        
         TreeNode* pHead = nullptr;
         pHead = buildTree(nums, 0, length-1);
         
         return pHead;
    }
    
    TreeNode* buildTree(vector<int>& nums, int left, int right){
        if(left > right)  //      （       left > right    ）
            return nullptr;
        
        int mid = (left + right) >> 1;
        TreeNode* pNode = new TreeNode(nums[mid]);
        
        if(left == right)  //       
            return pNode;
    
        pNode->left = buildTree(nums, left, mid-1);
        pNode->right = buildTree(nums, mid+1, right);
        
        return pNode;
    }
    
};

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[LeetCode] 157, Read 4 로 N 자 읽 기

제목 설명 파일 을 하나 드 리 고 이 파일 은 주어진 read 4 방법 으로 만 읽 을 수 있 습 니 다. n 문 자 를 읽 을 수 있 는 방법 을 실현 하 십시오.실제 읽 은 문자 갯 수 를 되 돌려 줍 니 다....

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[LeetCode] 108, 질서 있 는 배열 을 이 진 트 리 로 변환

좋은 웹페이지 즐겨찾기