귀속 문제 해결의 3부작

귀환은 프로그램이 자신을 반복적으로 호출하는 것이다. 이것은 프로그램의 각 단계의 기능이 똑같다는 것을 설명한다. 따라서 우리는 1급 귀환의 해결 과정을 주목하면 된다.
우리가 귀속 문제를 해결할 때 관심을 가져야 할 것은 주로 다음과 같은 세 가지이다.

전체 귀속의 종지 조건.

1급 귀환은 무엇을 해야 합니까?

상위 레벨에 대한 반환 값을 반환해야 합니다.

그래서 우리가 귀속문제를 풀 수 있는 세 곡이 생겼다.

전체 귀환의 종지 조건을 찾아라. 귀환은 언제 끝내야 합니까?

반환값 찾기: 상급자에게 어떤 정보를 반환해야 합니까?

본급 귀속은 무엇을 해야 합니까? 이 급 귀속에서 어떤 임무를 완성해야 합니까?

예1: 두 갈래 나무의 최대 깊이를 구하다
제목은 매우 간단하다. 두 갈래 나무의 최대 깊이를 구하면 문제 3부작 모형을 직접 세트로 귀속시킨다.

중지 조건을 찾습니다.어떤 상황에서 귀속적으로 끝납니까?물론 나무가 비어 있을 때 나무의 깊이가 0이면 귀환이 끝난다.

반환 값을 찾습니다.무엇을 되돌려야 합니까?제목은 나무의 최대 깊이를 구하는 것이다. 우리가 각 단계에서 얻어야 할 정보는 자연히 현재 이 등급에 대응하는 나무의 최대 깊이이다. 따라서 우리의 반환값은 현재 나무의 최대 깊이이다. 이 단계는 세 번째 단계와 결합해서 볼 수 있다.

본급 귀속은 무엇을 해야 합니까?이때 세 개의 노드가 있다. 루트, 루트->left, 루트->right이다. 그 중에서 두 번째 단계에 따라 루트->left와 루트->right는 각각 루트의 좌우 트리의 최대 깊이를 기록한다.그러면 본 단계의 귀환은 무엇을 해야 하는지 명확하다. 자연히 루트의 좌우 트리 중 비교적 큰 것을 선택하고 1은 루트를 뿌리로 하는 트리의 최대 깊이를 더한 다음에 이 깊이로 되돌아오면 된다.

반복 문제를 해결하는 c++ 코드는 다음과 같습니다.

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL)
            return 0;
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
    }
};

예2: 두 개의 교환 체인 테이블의 노드
3부작 템플릿을 직접 적용합니다.

중지 조건을 찾습니다.어떤 상황에서 귀속 중지합니까?교환할 수 있는 노드가 없을 때, 귀속이 종료됩니다.따라서 체인 시계가 한 개의 노드만 남았거나 노드가 없을 때 자연히 귀속은 끝난다.

반환 값을 찾습니다.우리는 상급 기관에 어떤 정보를 귀환하기를 희망합니까?우리의 목적은 두 개의 교환 체인 테이블 중 서로 인접한 노드이기 때문에 당연히 상급자에게 교환을 희망하는 것은 이미 교환 처리, 즉 이미 처리된 체인 테이블이다.

본급 귀속은 무엇을 해야 합니까?두 번째 단계와 결합하면 본 단계의 귀환만 고려하기 때문에 이 체인 시계는 우리의 눈에는 사실 세 개의 노드가 있다. 그것이 바로 헤드, 헤드->next, 이미 처리된 체인 시계 부분이다.이 단계에서 귀속되는 임무는 바로 이 세 노드 중의 앞의 두 노드를 교환하는 것이다.

이러한 문제를 해결하는 데 반복되는 c++ 코드는 다음과 같습니다.

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == NULL || head->next == NULL)
        {
            return head;
        }
        ListNode* next = head->next;
        head->next = swapPairs(next->next);
        next->next = head;
        return next;
    }
};

3부작으로 해결할 수 있는 문제들.
Leetcode 101. 대칭 두 갈래 나무
Leetcode 111. 두 갈래 나무의 최소 깊이
Leetcode 226. 두 갈래 나무를 뒤집다
Leetcode 617. 두 갈래 나무 결합
Leetcode 654. 최대 두 갈래 나무
Leetcode 83. 정렬 체인 테이블의 중복 요소 제거
Leetcode 206. 체인 테이블 뒤집기
유우린 블로그
전재 대상:https://www.cnblogs.com/gcheeze/p/10767308.html