[LeetCode] 107. Binary Tree Level Order Traversal II [JAVA(자바)]

문제 👉 <Binary Tree Level Order Traversal II - LeetCode>

1. 문제 (Binary Tree Level Order)

이진 트리의 루트가 주어지면 노드 값의 상향식(bottom-up) 순서 순회를 반환합니다. (i.e., from left to right, level by level from leaf to root)

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

2. 풀이

BFS 를 이용한 풀이

• Queue 에서 노드를 순서대로 꺼내 list 에 추가한다.
• Queue 에 left, right 순서로 자식 노드를 추가한다.
• Bottom-up 순서로 출력하기 위해 각 층을 나타나내는 list를 ret의 0번 인덱스에 추가한다.

3. 코드

/**
 * 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;

        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);

        while(!que.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = que.size();

            for (int i=0; i<size; i++) {
                TreeNode node = que.poll();
                level.add(node.val);
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);    
            }

            ret.add(0, level);  // 순회를 bottom-up 으로 넣기 위해 항상 0번 인덱스에 리스트 삽입
        }

        return ret;
    }
}

• 결과 :

Time Submitted	Status	Runtime	Memory	Language
05/03/2021	Accepted	1 ms	39 MB	java

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋