[LeetCode] 102. Binary Tree Level Order Traversal - 깊이우선탐색(DFS) + 넓이우선탐색(BFS) JAVA

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

코드설명

깊이우선탐색(DFS) + 넓이우선탐색(BFS) 을 활용합니다.

 

저는 DFS를 활용하였습니다만, BFS로 푸는것이 더 문제에 적합합니다. 이유는 BFS를 통해 한 단계 레벨씩 범위를 늘려가기 때문입니다.

혹은 중위순회로 트리를 배열로 만든뒤 2n+1, 2n+2 가 자식노드인 특성을 이용하는 방법도 가능합니다.

코드

DFS를 활용한 정답코드1입니다.

/**
 * 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>> list = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        DFS(root, 1);
        return list;
    }
    public void DFS(TreeNode now, int level){
        if(now == null){
            return ;
        }

        if(list.size() < level){
            list.add(new ArrayList<Integer>());
            list.get(level - 1).add(now.val);
        }else if(list.size() >= level){ 
            list.get(level - 1).add(now.val);
        }
        DFS(now.left, level + 1);
        DFS(now.right, level + 1);
        return ;
    }
}