두 갈래 나무 차원 이 관련 문제 를 두루 훑어보다

102. 두 갈래 나무의 층이 두루 다니다

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        vector> res;
        if(root==nullptr)
            return res;
        
        queue que;
        que.push(root);
        while(!que.empty()){
            int n = que.size(); // 
            vector level;
            for(int i=0;ival);
                if(tmp->left)
                    que.push(tmp->left);
                if(tmp->right)
                    que.push(tmp->right);
            }
            res.push_back(level);
            
        }
        return res;
    }
};

　　

107. 두 갈래 나무의 차원 훑어보기 II

두 갈래 나무를 정해서 노드 값이 밑에서 위로 올라가는 차원을 되돌려줍니다.(즉, 잎 노드가 있는 층에서 뿌리 노드가 있는 층으로 한 층씩 왼쪽에서 오른쪽으로 옮겨간다)
방법1: 대기열을 사용하여 매번 한 층을 훑어본 후 훑어본 결과를 헤더로 삽입합니다.2차원 그룹의 머리에 삽입하여 역순을 실현한다.

class Solution {
public:
    vector> levelOrderBottom(TreeNode* root) {
        vector> res;
        if(root==nullptr)
            return res;
        
        queue que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            vector level;
            for(int i=0;ival);
                if(tmp->left)
                    que.push(tmp->left);
                if(tmp->right)
                    que.push(tmp->right);
            }
            res.insert(res.begin(),level);
            
        }
        return res;
    }
};　　

실행 16ms
방법2 귀속 방법 사용(귀속을 통해 역순)

class Solution {
public:
    vector> levelOrderBottom(TreeNode* root) {
        vector> res;
        if(root==nullptr)
            return res;
        queue que;
        que.push(root);
        levelOrderBottom(que, res);
        return res;
        
    }
    void levelOrderBottom(queue que,vector>& res){
        if(que.empty())
            return;
        vector arr;
        queue queNext; // 
        while(!que.empty()){  // arr ， queNext 。 ， arr push res 
            TreeNode* tmp = que.front();
            que.pop();
            arr.push_back(tmp->val);
            if(tmp->left)
                queNext.push(tmp->left);
            if(tmp->right)
                queNext.push(tmp->right);    
        }
        
        levelOrderBottom(queNext, res);
        res.push_back(arr);
        return;
    }
};

　　
 

103. 두 갈래 나무의 톱날 모양 차원 횡단(지그재그)

방법1: 두 개의 창고 사용
두 개의 stack은 각각 한 층의 데이터를 저장한 다음에 선진적으로 나온 특성과 좌우 노드가 선후로 창고에 들어오는 순서 디테일(구체적으로 누가 먼저, 누가 나중에 코드를 볼 수 있는지)을 더하면 zigZag의 Z자형 접근 순서에 적절하게 대응할 수 있다.

 ， ， 。

class Solution {
public:
    vector> zigzagLevelOrder(TreeNode* root) {
        vector> res;
        if(root==nullptr)
            return res;
        
        stack sta1,sta2;
        vector arr;
        TreeNode* tmp = root;
        sta1.push(tmp);
        while(true){
            while(!sta1.empty()){
                tmp = sta1.top();
                sta1.pop();
                arr.push_back(tmp->val);
                if(tmp->left)
                    sta2.push(tmp->left);
                if(tmp->right)
                    sta2.push(tmp->right);
            }
            if(!arr.empty()){
                res.push_back(arr);
                arr.clear();  // 
            }      
            else
                break;
            
            while(!sta2.empty()){
                tmp = sta2.top();
                sta2.pop();
                arr.push_back(tmp->val);
                if(tmp->right)
                    sta1.push(tmp->right);
                if(tmp->left)
                    sta1.push(tmp->left);
                
            }
            if(!arr.empty()){
                res.push_back(arr);
                arr.clear();  // 
            }
            else
                break;
        }
        return res;
    }
};