Day 2

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

답(Java)

/**
 * 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>> list = new ArrayList<>();
        if (root == null)
            return list;
        Queue<TreeNode> curLevel = new LinkedList<>();
        curLevel.add(root);
        while (!curLevel.isEmpty()) {
            int size = curLevel.size();
            List<Integer> valueList = new ArrayList<>();
            for (int i = 0; i < size; ++i) {
                TreeNode curNode = curLevel.poll();
                valueList.add(curNode.val);
                if (curNode.left != null) {
                    curLevel.offer(curNode.left);
                }
                if (curNode.right != null) {
                    curLevel.offer(curNode.right);
                }
            }
            list.add(0, valueList);
        }
        return list;
    }
}

Binary tree의 Level order traversal을 위해 여러 가지 자료구조를 활용했다. 현재 level에 있는 노드의 자식들을 Queue에 삽입한다. 현재 level에 있는 노드를 탐색하면서 탐색한 노드의 번호를 List에 저장한다. 현재 level에 있는 모든 노드를 탐색했다면 번호를 담은 List를 저장하고 다음 level로 넘어간다. Tree의 모든 노드를 탐색하면 문제에서 요구한 결과를 리턴하고 종료한다.