.leetcode(958. Check Completeness of a Binary Tree)

https://leetcode.com/problems/check-completeness-of-a-binary-tree/

 

1. 2022.02.21 시도

소요시간: 79분(완전 이진트리 이해 시간  + 코딩)

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        int depth = 0;
        while(!queue.isEmpty()) {
            int limit = queue.size();
            for (int i=0; i<limit; i++){
                TreeNode node = queue.poll();

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            depth++;
        }

        queue.offer(root);
        int count = 0;
        while(!queue.isEmpty()) {
            int limit = queue.size();
            boolean c = false;
            for (int i=0; i<limit; i++){
                TreeNode node = queue.poll();
                if (node == null && count != depth-1) {
                    return false;
                } else  if (node == null) {
                    c = true;
                    continue;
                }
                if (c) {
                    return false;
                }
                queue.offer(node.left);
                queue.offer(node.right);
            }
            count++;
            if (count == depth) {
                break;
            }
        }
        
        return true;
    }
}

풀이 접근 과정

depth를 먼저 구했다.

그리고 null을 허용하면서 다시 순회를 했다. 대신 딱 depth까지만 돌도록 depth를 지정했다.

그리고 만약 depth전에 null이 있다면 그건 완전 이진 트리가 아니므로 false처리를 추가했다.

그리고 마지막 depth에서 null이 나왔다가 다시 숫자가 나오는 경우는 완전이지트리가 아니므로 boolean을 이용하여 체크하였다.

 

느낀점

• 완전 이진트리에 대한 이해가 부족했다.
• 나도 이 코드가 지저분하다는걸 너무나 잘 안다. 다만 솔루션을 보지 않고 풀긴 풀었다는데 의의를 둔다.
• null허용을 해서 순회를 돌릴 것인지 말 것인지, 마지막 depth에서 null여부체크를 어떻게 효율적으로 할 것인지가 어려웠다.
• 둘 다 잘 해내지 못하고 주먹구구식으로 해결하였다.
• 위의 아이디어에서 핵심만 뽑아서 솔루션으로 만들면 이렇게 될 것이다. 결국에 null이 나온 순간 부터 그 다음 null을 찾지 못하게 하면 된다.

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean c = false;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                c = true;
                continue;
            }
            if (c) {
                return false;
            }
            queue.offer(node.left);
            queue.offer(node.right);
        }
        
        return true;
    }
}

• dfs로 푸는 방법도 배웠다. bfs에서는 null체크이후에 다른 의미있는 노드가 있는지 확인하는 방법이었다면 dfs는 마지막 노드의 인덱스와 실제 노드 갯수를 비교하는 방법이다.

// dfs
//https://leetcode.com/problems/check-completeness-of-a-binary-tree/discuss/331342/Clean-and-Easy-Java-DFS-and-BFS-solution

class Solution {
    private int count;
    private int lastIndex;
    
    public boolean isCompleteTree(TreeNode root) {
        count = 0;
        lastIndex = 0;
        dfs(root, 1);
        return count == lastIndex;
    }
    
    private void dfs(TreeNode root, int index) {
        if (root == null) {
            return;
        }
        count++;
        
        lastIndex = Math.max(index, lastIndex);
        dfs(root.left, index*2);
        dfs(root.right, index*2+1);
    }
}

 

---

-알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형