[Leetcode(릿코드)] 107. Binary Tree Level Order Traversal II (Easy)

BFS 문제

leetcode.com/problems/binary-tree-level-order-traversal-ii/

Binary Tree Level Order Traversal II - LeetCode

---

문제 

이진트리를 BFS로 탐색한 후, 같은 레벨끼리 리스트로 묶어서 리턴하는 문제이다

 

해결

2가지 방식으로 풀었다

 

1. BFS로 탐색한 후, 가장 상위 레벨의 노드부터 호출하기 위해 스택에 담아 리턴한다

static void bfs(TreeNode treeNode, Stack<List<Integer>> stack) {

    Queue<List<TreeNode>> queue = new LinkedList<>();
    queue.add(List.of(treeNode));
    stack.push(List.of(treeNode.val));

    while (!queue.isEmpty()) {
        List<TreeNode> poll = queue.poll();
        List<TreeNode> queueList = new ArrayList<>();
        List<Integer> stackList = new ArrayList<>();

        for (TreeNode node : poll) {
            if (node.left != null) {
                queueList.add(node.left);
                stackList.add(node.left.val);
            }
            if (node.right != null) {
                queueList.add(node.right);
                stackList.add(node.right.val);
            }
        }

        if (!queueList.isEmpty()) queue.add(queueList);
        if (!stackList.isEmpty()) stack.push(stackList);
    }
}

2. 재귀

private static void recursion(TreeNode root, List<List<Integer>> levelTraversal, int level) {
    if(root == null) {
        return;
    }
    while(levelTraversal.size() <= level) {
        levelTraversal.add(new ArrayList<>());
    }
    levelTraversal.get(level).add(root.val);
    recursion(root.left, levelTraversal, level+1);
    recursion(root.right, levelTraversal, level+1);
}