Leet Code - 107. Binary Tree Level Order Traversal II(C++)

예제: Binary Tree Level Order Traversal II

문제
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,null,null,15,7],

return its bottom-up level order traversal as:

풀이

너비 우선 탐색 느낌이 나는 문제였다. 신기하게도 알고리즘 문제해결 전략에서 푼 문제와 비슷한 알고리즘을 쓰는 문제가 리트코드에서도 나올때가 있다.

BFS와 비슷하게, depth에 따라 queue에 node들을 넣어주며 vector에 저장하고, 후에 뒤집어서 return한다.

유의할 점이라고 하면, 처음 queue에 저장된 size 만큼만 vector에 저장해 주어야 depth별로 저장을 할 수 있다는 것이다.

전체적인 소스코드는 아래와 같다.

소스 코드

/* CASE 1 */
/**
 * 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>> res;

		if (root == NULL) return res;

		queue<TreeNode*> q;
		q.push(root);

		while (!q.empty()) {
			int size = q.size();
			vector<int> v;

			for (int i = 0; i < size; i++) {
				TreeNode* front = q.front();
				q.pop();

				v.push_back(front->val);
				if (front->left != NULL)
					q.push(front->left);
				if (front->right != NULL)
					q.push(front->right);
			}

			res.push_back(v);
		}

		reverse(res.begin(), res.end());
		return res;
	}
};

풀이 후기

재귀함수에 너무 익숙해져 버린 필자는 처음에 재귀함수로 풀었다. 풀리긴 풀리나, 역시 위와 같은 방법으로 푼 것이 속도가 더 빨랐다.
재귀함수를 사용한 문제를 많이 풀다보니, 항상 재귀함수를 적용하는 방향으로 접근하려는 버릇이 생긴걸까. 재귀함수에 집착하지 말자!