LetCode 94 두 갈래 나무에서 순서대로 반복되는 비귀속 통속적이고 알기 쉬운 만능 템플릿 방법

LetCode 94 두 갈래 나무에서 순서대로 반복되는 비귀속 통속적이고 알기 쉬운 만능 템플릿 방법

1.두 갈래 나무에 차례로 옮겨다니기

2.비귀속 두 갈래 트리에서 만능 템플릿법

두 갈래 나무의 스트리밍 방식은 면접에서 인기 있는 시험지로서 스트리밍 방식은 모두가 쉽게 쓸 수 있다고 믿지만 스트리밍 방법만 파악하는 것은 부족하다. 또한 비스트리밍 방식을 파악하고 전, 중, 후 세 가지 스트리밍을 해결할 수 있는 비스트리밍 형식의 모델을 소개한다.비귀속 문제를 한꺼번에 해결하라!!
앞뒤 범람하는 만능 모형법 뒤뒤 범람하는 만능 모형법

1. 두 갈래 나무에 차례대로

중서가 두루 흐르는 순조로운 것은 왼쪽 나무, 뿌리 노드, 오른쪽 나무다.귀환은 주로 귀환 구조와 귀환 종결 조건이다.
귀속 구조: 그러면 귀속의 순서는 먼저 왼쪽 나무를 훑어보고 뿌리 노드를 보존하며 오른쪽 나무를 훑어보는 것이다.귀속 종료 조건: 명확한 종료 조건이 없기 때문에 귀속 조건은 NULL을 만나면 귀환하면 된다.

class Solution {
    
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        func(root,res);
        return res;        
    }
    
    void func(TreeNode* root, vector<int>& res)
    {
        if(root==NULL)	  
            return ;
        func(root->left,res);		  
        res.push_back(root->val);     
        func(root->right,res);		  
    }
};

2. 비귀속 두 갈래 나무 중 순서대로 만능 템플릿법

비귀속법에 대해 난이도가 높을 수 있기 때문에 우리는 귀속 방식을 창고의 데이터 구조를 사용하여 귀속을 모의할 것이다.
만능 템플릿법 역시 창고의 데이터 구조를 빌려쓰는 동시에 우리는 하나의 종류를 도입하여 추가 정보를 제공한다.
Guide 클래스를 도입했습니다.

class Guide{ 
public:
    int ope;
    TreeNode* node;
    Guide(int ope,TreeNode* node):ope(ope),node(node){}  
};

우리는 창고를 사용하는 과정에서 트리 노드를 저장하지 않고 가이드 클래스의 대상을 저장한다. 가이드 클래스의 대상은 트리 노드와 추가 정보(int ope)를 포함하고 실제로ope는 두 가지 수치만 있다. 0과 1이다.ope=0은 우리가 처음으로 어떤 나무 노드를 훑어보았다는 것을 의미한다(우리가 처음 훑어본 어떤 노드는 세 가지 유형의 조작이 있다)

현재 노드의 값을 최종 결과에 저장한다(즉ope의 값을 1).

왼쪽 나무를 두루 돌아다닌다.

오른쪽 나무를 두루 돌아다닌다.

중서가 왼쪽, 뿌리, 오른쪽에 두루 걸쳐 있다.그래도 창고에 넣는 순서는 오른쪽, 뿌리, 왼쪽입니다.대응하는 핵심 코드

st.push(Guide(0,s.node->right));
st.push(Guide(1,s.node));
st.push(Guide(0,s.node->left));

ope = 1은 이 대상에 포함된 트리 노드의 값을 최종vector에 저장하는 것을 의미합니다.
그러면 최종 완성판 코드는 다음과 같다.앞의 순서, 뒤의 순서가 반복되지 않는 것은 상술한 세 문장의 순서를 바꾸기만 하면 된다.

class Guide{
public:
    int ope;
    TreeNode* node;
    Guide(int ope,TreeNode* node):ope(ope),node(node){}    
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL)
            return res;
        stack<Guide> st;
        st.push(Guide(0,root));
        while(!st.empty())
        {
            Guide s = st.top();
            st.pop();
            if(s.node == NULL)
                continue;
            if(s.ope == 1)
            {
                res.push_back(s.node->val);
            }else{
                st.push(Guide(0,s.node->right));
                st.push(Guide(1,s.node));
                st.push(Guide(0,s.node->left));
            }
        }  
        return res;
    }    
};