[leetcode #102] Binary Tree Level Order Traversal

Problem

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

· The number of nodes in the tree is in the range [0, 2000].
· -1000 <= Node.val <= 1000

Idea

Tree를 탐색하는 세 가지 방법 중 하나를 택해 node를 탐색하면서 level 또한 재귀함수의 인자로 넣어준다.

List의 크기가 level보다 작거나 같을 경우 현재 노드의 값을 List로 만들어 List의 level번째 원소로 넣어준다.

이미 level번째 원소가 있을 경우 해당 리스트를 꺼낸 뒤 노드 값을 더해주면 된다.

Solution

/**
 * 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 {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        traverse(root, 0);

        return res;
    }

    private void traverse(TreeNode node, int level) {
        if (node == null) {
            return;
        }

        if (res.size() <= level) {
            res.add(new ArrayList<>(Arrays.asList(node.val)));
        } else {
            res.get(level).add(node.val);
        }

        traverse(node.left, level+1);
        traverse(node.right, level+1);
    }
}

Reference

https://leetcode.com/problems/binary-tree-level-order-traversal/