이진 트리, Binary Tree Level Order Traversal

Problems

• 102. Binary Tree Level Order Traversal(사실상 level이 출력되는 순서만 다름)
• 107. Binary Tree Level Order Traversal II(Current problem)

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).

문제 해석

트리를 순회하면서 레벨별로 왼쪽 에서 오른쪽 아래애서 위 방향으로 노드를 출력하다

문제 접근

• Binary Tree를 level별로 접근 -> BFS!
• BFS를 어떻게 구현할까? -> queue로 구현!

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
	    List<List<Integer>> ret = new ArrayList<>();
		if(root == null) return ret;

		Quene<TreeNode> q = new ArrayList<>();
		q.offer(root);

		while(!q.isEmpty()){
			List<Integer> level = new ArrayList<>();
			int size = q.size();
			for(int i=0; i<size; i++){
				TreeNode node = q.poll();
				level.add(node.val);
				if(node.left != null) q.offer(node.left);
				if(node.right != null) q.offer(node.right);
			}
			ret.add(0, level);
			// 102 문제에서는 ret.add(level);
		}
		return ret;
    }
}