leetcode102 두 갈래 나무의 차원 반복

1385 단어

제목:


두 갈래 트리를 정해서 차원별로 훑어보는 노드 값을 되돌려줍니다.(즉, 왼쪽에서 오른쪽으로 모든 노드에 층층이 접근한다.)
예를 들어 두 갈래 나무를 주면[3,9,20,null,null,15,7],
   3
   / \
 9  20
    /  \
  15   7

다음 단계를 반복한 결과를 반환합니다.
[
  [3],
  [9,20],
  [15,7]
]

생각:


바로 트리의 BFS입니다. 출력 요구는 층마다 출력하기 때문에 n = q.size() 를 취하고 층마다 n번 조작을 하면 층마다 답을 저장할 수 있습니다.

코드:

/**
 * 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> levelOrder(TreeNode* root) {
        vector> ans;
        queue q;
        q.push(root);
        int k = 1;
        TreeNode* u;
        while(!q.empty()){
            vector vec;
            int n = q.size();
            for(int i = 0; i < n; ++i){
                if(q.empty()) { break; } 
                u = q.front(); q.pop();
                if(u!=NULL) {
                    vec.push_back(u->val);
                    q.push(u->left);
                    q.push(u->right);
                }
            }
            if(vec.size() != 0) ans.push_back(vec);
        }
        return ans;
    }
};

좋은 웹페이지 즐겨찾기