C++LeetCode 구현(107.이 진 트 리 층 차 를 옮 겨 다 니 는 2)

[LeetCode]107.Binary Tree Level Order Traversal II 이 진 트 리 층 차 를 옮 겨 다 니 는 2
Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).
Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
Constraints:

The number of nodes in the tree is in the range [0, 2000].

-1000 <= Node.val <= 1000

밑 에 층 차 를 옮 겨 다 니 는 것 은 윗부분 부터 옮 겨 다 니 는 것 입 니 다.마지막 에 저장 하 는 방식 이 바 뀌 었 을 뿐 블 로 거들 의 이전 블 로 거 를 참조 할 수 있 습 니 다Binary Tree Level Order Traversal참조 코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    vector<vector<int> > levelOrderBottom(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.insert(res.begin(), oneLevel);
        }
        return res;
    }
};

다음은 재 귀적 해법 을 살 펴 보 겠 습 니 다.재 귀적 특성 으로 인해 우 리 는 왼쪽 노드 를 먼저 처리 할 것 입 니 다.그러면 반드시 서로 다른 층 을 통과 할 것 입 니 다.그래서 특정한 노드 를 넣 으 려 면 현재 의 깊이 를 알 아야 합 니 다.따라서 하나의 변수 level 을 사용 하여 현재 의 깊이 를 표시 하고 0 을 초기 화하 여 뿌리 노드 가 있 는 깊이 를 표시 합 니 다.2 차원 배열 res 를 되 돌려 야 하기 때문에 처음에는 이 진 트 리 의 깊이 를 모 르 고 몇 층 이 있 는 지 모 르 기 때문에 2 차원 배열 의 크기 를 잘 신청 할 수 없고 옮 겨 다 니 는 과정 에서 만 계속 증가 합 니 다.그러면 언제 새로운 층 을 신청 해 야 합 니까?level 이 2 차원 배열 의 크기 와 같 을 때 왜 같 습 니까?현재 의 깊이 를 초과 하 겠 다 고 하지 않 았 습 니까?이것 은 level 이 0 에서 시작 되 었 기 때 문 입 니 다.마치 길이 가 n 인 배열 A 와 같 습 니 다.A[n]를 방문 하면 오류 가 발생 할 수 있 습 니 다.level 이 배열 의 길이 와 같 을 때 새로운 신청 이 필요 합 니 다.빈 층 을 새로 만 들 고 숫자 를 계속 추가 합 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        levelorder(root, 0, res);
        return vector<vector<int>> (res.rbegin(), res.rend());
    }
    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/107
유사 한 제목:
Average of Levels in Binary Tree
Binary Tree Zigzag Level Order Traversal
Binary Tree Level Order Traversal
유사 한 제목:
https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
https://leetcode.com/problems/binary-tree-level-order-traversal-ii/discuss/35089/Java-Solution.-Using-Queue
https://leetcode.com/problems/binary-tree-level-order-traversal-ii/discuss/34981/My-DFS-and-BFS-java-solution
C++구현 LeetCode(107.이 진 트 리 층 차 를 옮 겨 다 니 는 2)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 이 진 트 리 층 차 를 옮 겨 다 니 는 2 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!