문제 설명

두 갈래 나무와 그 중의 한 결점을 정하십시오. 순서를 반복하는 다음 결점을 찾아 돌아오십시오.나무의 결점은 좌우 자결점뿐만 아니라 부모 결점을 가리키는 바늘도 포함하고 있음을 주의하십시오.

문제 풀이 보고서

먼저 이 노드t에 오른쪽 트리가 있는지 확인합니다.

이 없으면 이 노드의 부모 노드p로 돌아가 노드p의 오른쪽 아이가 노드t인지 확인해야 한다. 만약, 소급법 노드p라면 같은 조작을 계속해야 한다. 그렇지 않으면 현재 노드의 아버지 노드로 돌아간다.

이 있다면 이 노드의 오른쪽 나무의 가장 왼쪽 노드는 노드t의 다음 노드이다.

구현 코드

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if(pNode->right==nullptr){
            while(pNode->next!=nullptr&&pNode->next->right==pNode){
                pNode=pNode->next;
            }
            if(pNode->next==nullptr) return nullptr;
            else return pNode->next;
        }
        else{
            TreeLinkNode* root=pNode->right;
            while(root->left){
                root=root->left;
            }
            return root;
        }
        return nullptr;
    }
};

참고 자료

[1] 우객 - JZ 57 두 갈래 나무의 다음 노드

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

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

우객 - JZ 57 두 갈래 나무의 다음 노드 [두 갈래 나무의 중서 역행]

기사 목록 문제 설명 문제 풀이 보고서 구현 코드 참고자료 두 갈래 나무와 그 중의 한 결점을 정하십시오. 순서를 반복하는 다음 결점을 찾아 돌아오십시오.나무의 결점은 좌우 자결점뿐만 아니라 부모 결점을 가리키는 바...

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

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

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다