C++LeetCode 구현(102.이 진 트 리 순서 옮 겨 다 니 기)

[LeetCode]102.바 이 너 리 트 리 레벨 Order Traversal 이 진 트 리 층 차 를 옮 겨 다 니 며
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
    3
/ \
9  20
/  \
15   7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
층 차 가 이 진 트 리 를 옮 겨 다 니 는 것 은 전형 적 인 범위 에서 BFS 를 우선 검색 하 는 응용 이다.그러나 여기 서 조금 복잡 한 것 은 각 층 의 수 를 나 누 어 2 차원 벡터 에 저장 해 야 한 다 는 것 이다.대체적으로 생각 이 똑 같 고 하나의 quue 를 만 든 다음 에 뿌리 노드 를 먼저 넣 는 것 이다.이때 뿌리 노드 의 좌우 두 개의 노드 를 찾 아야 한다.이때 뿌리 노드 를 없앤다.이때 queue 의 요 소 는 바로 다음 층 의 모든 노드 입 니 다.하나의 for 순환 으로 그것들 을 옮 겨 다 닌 다음 에 1 차원 벡터 에 저장 합 니 다.옮 겨 다 닌 후에 이 1 차원 벡터 를 2 차원 벡터 에 저장 합 니 다.이런 식 으로 유추 하면 층 차 를 옮 겨 다 닐 수 있 습 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> res;
        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
            vector<int> oneLevel;
            for (int i = q.size(); i > 0; --i) {
                TreeNode *t = q.front(); q.pop();
                oneLevel.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            res.push_back(oneLevel);
        }
        return res;
    }
};

다음은 재 귀적 인 문법 을 살 펴 보 자.핵심 은 2 차원 배열 과 하나의 변수 level 이 필요 하 다 는 것 이다.level 의 역할 은 블 로 거들 의 다른 블 로 그 를 참조 할 수 있다.  Binary Tree Level Order Traversal II  다음 코드 를 참조 하 십시오.
해법 2:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        levelorder(root, 0, res);
        return res;
    }
    void levelorder(TreeNode* node, int level, vector<vector<int>>& res) {
        if (!node) return;
        if (res.size() == level) res.push_back({});
        res[level].push_back(node->val);
        if (node->left) levelorder(node->left, level + 1, res);
        if (node->right) levelorder(node->right, level + 1, res);
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/102
유사 한 제목:
Binary Tree Level Order Traversal II
Binary Tree Zigzag Level Order Traversal
Minimum Depth of Binary Tree
Binary Tree Vertical Order Traversal  
Average of Levels in Binary Tree
N-ary Tree Level Order Traversal
참고 자료:
https://leetcode.com/problems/binary-tree-level-order-traversal/
https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/33445/Java-Solution-using-DFS
https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/33450/Java-solution-with-a-queue-used
https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/114449/A-general-approach-to-level-order-traversal-questions-in-Java
C++구현 LeetCode(102.이 진 트 리 층 차 를 옮 겨 다 니 며)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 이 진 트 리 층 차 를 옮 겨 다 니 는 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!