[Java] Daily LeetCode Challenge 958. Check Completeness of a Binary Tree

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

Check Completeness of a Binary Tree - LeetCode

 

※ 경우에 따라 체크해야 할 사항

1. Leaf가 아닌 경우 

   현재 Level에 맞게 Node 개수가 있어야 함 (2^n개)

2. Leaf인 경우

   왼쪽 정렬 

 

[코드]

/**
 * 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 int leafLevel = 0;
    public HashMap<Integer, ArrayList<TreeNode>> hm = new HashMap<>();
    public boolean isCompleteTree(TreeNode root) {
        dfs(root, 0);

        for(int i=0; i<leafLevel; i++){
            if(hm.get(i).size() != Math.pow(2, i))
                return false;
        }

        if(leafLevel == 0)
            return true;

        boolean complete = false;
        ArrayList<TreeNode> par = hm.get(leafLevel-1);

        for(TreeNode tn : par){
            if(complete && (tn.left != null || tn.right != null))
                return false;
            
            if(tn.left == null || tn.right == null)
                complete = true;

            if(tn.left == null && tn.right != null)
                return false;
        }

        return true;
    }

    public void dfs(TreeNode tn, int dep){
        ArrayList<TreeNode> arr = hm.getOrDefault(dep, new ArrayList<TreeNode>());
        arr.add(tn);
        hm.put(dep, arr);
        leafLevel = Math.max(leafLevel, dep);

        if(tn.left != null)
            dfs(tn.left, dep+1);
        if(tn.right != null)
            dfs(tn.right, dep+1);
    }

}