C++LeetCode 구현(145.이 진 트 리 의 뒷 순 서 를 옮 겨 다 니 기)

[LeetCode]145.Binary Tree Postorder Traversal 이 진 트 리 의 뒷 순 서 를 옮 겨 다 닙 니 다.
Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
   1
\
2
/
3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
전형 적 인 제목 은 이 진 트 리 의 뒷 순 서 를 구 하 는 비 재 귀 방법 입 니 다.앞 순서,중간 순서,층 서 는 모두 스 택 을 사용 해 야 합 니 다.뒷 순 서 는 왼쪽-오른쪽-뿌리 이기 때문에 하나의 결점 값 이 추출 되 었 을 때 왼쪽 과 오른쪽 결점 이 존재 하지 않 거나 이미 방문 되 었 습 니 다.먼저 뿌리 결산 점 을 창고 에 넣 은 다음 에 보조 결산 점 head 를 정의 합 니 다.while 순환 의 조건 은 창고 가 비어 있 지 않 습 니 다.순환 중 에 먼저 창고 꼭대기 결산 점 t 를 꺼 냅 니 다.만약 에 창고 꼭대기 결산 점 이 좌우 자 결산 점 이 없 거나 왼쪽 자 결산 점 이 head 이거 나 오른쪽 자 결산 점 이 head 인 경우.스 택 꼭대기 결산 점 값 을 결과 res 에 추가 하고 스 택 꼭대기 요 소 를 스 택 에서 옮 긴 다음 에 head 를 스 택 꼭대기 요 소 를 가리 킵 니 다.그렇지 않 으 면 오른쪽 결산 점 이 비어 있 지 않 으 면 스 택 에 가입 하고 왼쪽 결산 점 이 비어 있 지 않 으 면 스 택 에 가입 하 는 것 을 볼 수 있 습 니 다.여기 서 오른쪽,왼쪽 순 서 는 스 택 에 들 어간 후에 먼저 나 오 는 특징 때문에 왼쪽 결산 점 이 먼저 처 리 될 수 있 습 니 다.다음은 왜 이 세 가지 조건 인지 살 펴 보 겠 습 니 다.먼저 스 택 꼭대기 요소 가 좌우 자 결산 점 이 없 으 면 잎 결산 점 임 을 설명 합 니 다.그리고 스 택 에 들 어 가 는 순 서 는 왼쪽 자 결산 점 이 먼저 처리 되 는 것 을 보장 합 니 다.그래서 이때 의 결산 점 수 치 는 결과 res 에 직접 가입 한 다음 에 스 택 을 옮 겨 헤드 를 이 잎 결산 점 을 가리 킬 수 있 습 니 다.이렇게 되면 헤드 는 매번 앞의 처 리 를 가리 키 고 결과 res 의 결산 점 을 추가 합 니 다.만약 에 창고 꼭대기 결산 점 의 왼쪽 결산 점 이나 오른쪽 결산 점 이 헤드 라면 그 하위 결산 점 이 결과 res 에 가입 했다 는 것 을 의미 합 니 다.그러면 현재 결산 점 을 처리 할 수 있 습 니 다.
여기 서 헤드 에 대한 역할 과 루트 로 초기 화 하 는 이 유 는 잘 모 르 겠 습 니 다.여기 서 다시 설명 하 겠 습 니 다.head 는 이전 에 옮 겨 다 니 며 완 성 된 결산 점 을 가리 키 는 것 입 니 다.후 서 를 옮 겨 다 니 는 순서 가 왼쪽-오른쪽-뿌리 이기 때문에 반드시 결산 점 을 창고 에 넣 고 가장 왼쪽 결산 점(또는 가장 왼쪽 결산 점 의 가장 오른쪽 결산 점)을 창고 에 넣 은 후에 처 리 를 시작 합 니 다.일단 처 리 를 시작 하면 헤드 는 다시 값 을 부여 받는다.따라서 head 초기 화 값 은 큰 영향 을 미 치지 않 습 니 다.유일 하 게 주의해 야 할 것 은 빈 것 으로 초기 화 할 수 없습니다.현재 노드 를 인쇄 할 지 여 부 를 판단 할 때 잎 결점 여 부 를 판단 하 는 것 외 에 head 가 좌우 자 결점 을 가리 키 는 지 여 부 를 봐 야 합 니 다.만약 에 head 가 왼쪽 자 결점 을 가리 키 면 오른쪽 자 결점 은 반드시 비어 있 습 니 다.스 택 에 들 어 가 는 순 서 는 뿌리-오른쪽-왼쪽 이기 때 문 입 니 다.오른쪽 결점 이 처리 되 기도 전에 뿌리 결점 을 직접 처리 하 는 경 우 는 없다.헤드 가 오른쪽 결점 을 가리 키 면 정상 적 인 왼쪽-오른쪽-뿌리의 처리 순서 입 니 다.그러면 돌 이 켜 보면 head 가 비어 있 고 이때 마침 왼쪽 노드 가 존재 하지 않 는 다 면 뿌리 노드 를 눌 렀 을 때 head 와 왼쪽 노드 가 같 으 면 성립 된다.이때 뿌리 노드 를 직접 인쇄 하 는 것 은 분명 잘못된 것 이다.그래서 헤드 가 비어 있 는 것 으로 초기 화 되 지 않 으 면 모든 것 이 말 할 수 있 고 심지 어 는 결점 을 새로 만 들 수도 있다.head 를 root 로 초기 화 하 셔 도 됩 니 다.하나의 root 결점 만 있 더 라 도 잎 결점 을 판정 할 때 root 를 인쇄 한 다음 while 순환 에서 뛰 어 내 려 도 오류 가 발생 하지 않 습 니 다.코드 는 다음 과 같 습 니 다:
해법 1:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s{{root}};
        TreeNode *head = root;
        while (!s.empty()) {
            TreeNode *t = s.top();
            if ((!t->left && !t->right) || t->left == head || t->right == head) {
                res.push_back(t->val);
                s.pop();
                head = t;
            } else {
                if (t->right) s.push(t->right);
                if (t->left) s.push(t->left);
            }
        }
        return res;
    }
};

후 서 를 옮 겨 다 니 는 순 서 는 왼쪽-오른쪽-뿌리 이기 때문에 먼저 옮 겨 다 니 는 순 서 는 뿌리-왼쪽-오른쪽 이 고 두 가 지 는 비슷 합 니 다.먼저 먼저 옮 겨 다 니 는 방법 에 작은 변경 을 해서 옮 겨 다 니 는 순 서 를 뿌리-오른쪽-왼쪽 으로 바 꾸 고 뒤 집 으 면 왼쪽-오른쪽-뿌리 입 니 다.뒤 집 는 방법 은 저희 가 역방향 Q 를 사용 할 수 있 습 니 다.아 닙 니 다.역방향 으로 결 과 를 넣 는 res 입 니 다.매번 결과 res 의 시작 부분 에 노드 값 을 추가 하고 먼저 스 택 에 들 어 가 는 순 서 를 바 꾸 면 스 택 에 들 어 가 는 순 서 를 옮 겨 다 니 고 왼쪽,오른쪽,이렇게 스 택 에서 처리 할 때 오른쪽,왼쪽 입 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s{{root}};
        while (!s.empty()) {
            TreeNode *t = s.top(); s.pop();
            res.insert(res.begin(), t->val);
            if (t->left) s.push(t->left);
            if (t->right) s.push(t->right);
        }
        return res;
    }
};

그러면  Binary Tree Preorder Traversal  중의 해법 2 도 바 꿀 수 있 습 니 다.바 꾸 는 사 고 는 위의 해법 과 마찬가지 로 먼저 순서대로 옮 겨 다 니 는 뿌리-왼쪽-오른쪽 순 서 를 뿌리-오른쪽-왼쪽 으로 바 꾸 고 뒤 집어 서 옮 겨 다 니 는 왼쪽-오른쪽-뿌리 로 바 꿉 니 다.뒤 집어 서 결과 res 의 가입 순 서 를 바 꿉 니 다.그 다음 에 업데이트 보조 결점 p 의 좌우 순 서 를 바 꾸 면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 3:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while (!s.empty() || p) {
            if (p) {
                s.push(p);
                res.insert(res.begin(), p->val);
                p = p->right;
            } else {
                TreeNode *t = s.top(); s.pop();
                p = t->left;
            }
        }
        return res;
    }
};

포럼 에 더 블 스 택 의 해법 도 있 습 니 다.사실은 본질 적 으로 해법 2 와 다 를 것 이 없습니다.모두 선착순 으로 옮 겨 다 니 는 순 서 를 바 꾸 어 후 서 를 옮 겨 다 니 는 것 입 니 다.코드 는 다음 과 같 습 니 다.
해법 4:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s1, s2;
        s1.push(root);
        while (!s1.empty()) {
            TreeNode *t = s1.top(); s1.pop();
            s2.push(t);
            if (t->left) s1.push(t->left);
            if (t->right) s1.push(t->right);
        }
        while (!s2.empty()) {
            res.push_back(s2.top()->val); s2.pop();
        }
        return res;
    }
};

C++구현 LeetCode(145.이 진 트 리 의 뒷 순 서 를 옮 겨 다 니 며)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 이 진 트 리 의 뒷 순 서 를 옮 겨 다 니 는 내용 은 예전 의 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!