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

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

코드설명

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

 

기본적으로 bottom-up level order 로 출력해야 하므로 ArrayList의 add(0, value) 값을 통해 addFirst() 와 같은 형태로 사용합니다. 내가 원하는 위치에 넣을 수 있는 기능이지요.

이를 통해, 순서를 뒤집어서 저장할 수 있고, 기본적으로 새로 삽입하는 값들을 모두 맨 앞에 삽입하도록 하면 bottom-up 방식으로 될 것 입니다. 

 

처음에 패착은, DFS에서 모든 로직을 탄뒤에 반환하면서 처리해야 bottom-up 방식으로 구현하기 훨씬 편하다고 생각했는데, ArrayList의 addFirst() 의 기능을 add(0, 값)의 형태로 사용하면 BFS와 DFS를 거의 같은 방식으로 구현할 수 있습니다.

코드

BFS를 활용한 정답코드2입니다.

/**
 * 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>> answer = new ArrayList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null) return answer;
        BFS(root);
        return answer;
    }

    void BFS(TreeNode node){
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(node);
        while(!q.isEmpty()){
            int size = q.size();
            List<Integer> level = new ArrayList<>();

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

}

 

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

아래의 오류코드를 개선시킨 코드입니다. 

핵심은, list의 size가 level보다 작을때, 새로 list에 값을 추가하되 아래 Level부터 출력해야하므로 list.add(0, new ArrayList<>()); 를 통해 맨 앞에 새로운 ArrayList를 추가해줍니다.

bottom-up level order이기에 아래와 같이 list.size() - level -1  로 인덱스를 처리해줍니다. 가장 맨 아래 level이 맨 앞에 오도록 처리하는 것이지요.

list.get(list.size() - level - 1).add(node.val);

 

/**
 * 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>> answer = new ArrayList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null) return answer;
        DFS(0, root, answer);
        return answer;
    }
    
    void DFS(int level, TreeNode node, List<List<Integer>> list){
        if(node == null) return;
        if(list.size() <= level) list.add(0, new ArrayList<>());
        DFS(level + 1, node.left, list);
        DFS(level + 1, node.right, list);
        list.get(list.size() - level - 1).add(node.val);
    }
}

처음에 잘못 푼 코드입니다. 

이 코드의 경우 아래와 같이 입력이 들어왔을때,

[1,2,3,4,null,null,5]

정답은 아래와 같이 나와야합니다만,

[[4, 5], [2, 3], [1]]

제 코드는 같은 레벨임에도 다른 배열에 처리됩니다.

[[4],[5],[2,3],[1]]

원인은, DFS가 분기되면서 서로 각 자식의 노드만 포함하기 때문입니다. 같은 레벨을 모두 고려하는 것이 아니지요.

/**
 * 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>> answer = new ArrayList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null) return answer;

        DFS(root);
        List<Integer> arr = new ArrayList<>();
        arr.add(root.val);
        answer.add(arr);
        return answer;
    }

    int DFS(TreeNode node){
        List<Integer> arr = new ArrayList<>();
        if(node.left != null){
            arr.add(DFS(node.left));
        }
        if(node.right != null){
            arr.add(DFS(node.right));
        }
        if(arr.size() > 0)
            answer.add(arr);
        return node.val;
    }
}