LeetCode 107 Binary Tree Level Order Traversal II(두 갈래 나무의 계층 순서 반복 2)(*)

번역하다

 ， 。

 ， 。

 ：
  {3,9,20,#,#,15,7}，
    3
   / \
  9  20
    /  \
   15   7
 ：
[
  [15,7],
  [9,20],
  [3]
]

원문

Given a binary tree, return the bottom-up level order traversal of its nodes' values. 

(ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

분석

사실은 위에서 아래로 하든 아래에서 위로 하든 상관없어요. 마지막에 반전을 하면 돼요. 관건은 어떻게 훑어보는 거예요.
나는 처음에 문제의 뜻을 잘 이해하지 못했는데, 결과는 노드 아래의 두 잎에 따라vector에 추가되었는데, 후에 원래는 등급에 따라야 한다는 것을 발견하였다.
그래서 선진적으로 먼저 나온 대열을 사용했고 대열에 두 갈래 나무의 등급 정보를 포함해야 하기 때문에pair를 구축했다.

vector<vector<int>> vecAns;
if (!root) return vecAns;
queueint, TreeNode*>> queueTree;

먼저 마지막에 되돌려주는vecAns를 정의한 다음에 루트가 비어 있는지 판단합니다. 그렇다면 직접 되돌려주고 추가 작업을 하지 않습니다.구성된queue에서 int는 계층 정보를 저장하고 TreeNode*는 노드를 저장합니다.
다음은 맵을 정의합니다. 맵의 장점은 언제든지 키를 지정하여 값을 추가할 수 있다는 것입니다. 여기는 바로 등급을 지정하여 정보를 추가하는 것입니다. 뒤에 있는vector는 트리 노드를 저장하는 데 사용됩니다.root의 레벨을 0으로 설정하고 뒤에make_pair는pair를 구성합니다. 마지막으로queue에 추가합니다.

map<int, vector<int>> mapAns;
int rootLevel = 0;
queueTree.push(make_pair(rootLevel, root));

queue가 비어 있지 않으면 계속 순환합니다.매번 시작할 때마다 현재 대기열의 맨 위에 있는 등급 정보와 현재 노드를 분석하여 맵에 추가합니다.추가가 끝나면 팝업할 수 있습니다.왼쪽 트리를 계속 판단하고 비우면queue에 추가해서 다음 작업을 기다립니다.다음 순환을 기다리면 맵에 추가합니다.

while (!queueTree.empty()) {
    int currentLevel = (queueTree.front().first);
    TreeNode *currentNode = (queueTree.front().second);
    mapAns[currentLevel].push_back(currentNode->val);
    queueTree.pop();
    if (currentNode->left != NULL)
        queueTree.push(make_pair(currentLevel + 1, currentNode->left));
    if (currentNode->right != NULL)
        queueTree.push(make_pair(currentLevel + 1, currentNode->right));
}

맵의 정보를 하나하나push를vector에 넣고 마지막에 바로 리턴합니다.

for (auto iter = mapAns.rbegin(); iter != mapAns.rend(); ++iter) {
    vecAns.push_back(iter->second);
}
return vecAns;

Ok, 여러분은 이전 문제를 보실 수 있습니다.
LeetCode 102 Binary Tree Level Order Traversal(두 갈래 나무의 계층 순서 반복)(*)

코드

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode *root) {
        vector<vector<int>> vecAns;
        if (!root) return vecAns;
        queueint, TreeNode*>> queueTree;
        map<int, vector<int>> mapAns;
        int rootLevel = 0;
        queueTree.push(make_pair(rootLevel, root));
        while (!queueTree.empty()) {
            int currentLevel = (queueTree.front().first);
            TreeNode *currentNode = (queueTree.front().second);
            mapAns[currentLevel].push_back(currentNode->val);
            queueTree.pop();
            if (currentNode->left != NULL)
                queueTree.push(make_pair(currentLevel + 1, currentNode->left));
            if (currentNode->right != NULL)
                queueTree.push(make_pair(currentLevel + 1, currentNode->right));
        }
        for (auto iter = mapAns.rbegin(); iter != mapAns.rend(); ++iter) {
            vecAns.push_back(iter->second);
        }
        return vecAns;
    }
};