222. Count Complete Tree Nodes

이진 트리에서 노드의 수를 세는 문제입니다. 

이 문제에서는 완전 이진 트리의 루트가 주어지고, 트리에 있는 노드의 수를 반환해야 합니다.

완전 이진 트리는 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 모든 노드는 가능한 한 왼쪽에 있습니다.

마지막 레벨 h에서 노드의 수는 1과 2h 사이입니다.

이 문제를 해결하기 위한 알고리즘은 O(n)보다 작은 시간 복잡도를 가져야 합니다.

예시:

예시 1: 입력: root = [1,2,3,4,5,6], 출력: 6
예시 2: 입력: root = [], 출력: 0
예시 3: 입력: root = 1, 출력: 1
제약 조건:

트리의 노드 수는 범위 [0, 5 * 10^4] 내에 있습니다.
0 <= Node.val <= 5 * 10^4

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    private int count = 0;
    public int CountNodes(TreeNode root) {
        PreOrder(root);
        return count;
    }
    private void PreOrder(TreeNode node){
        if(node == null) return;

        count++;
        PreOrder(node.left);
        PreOrder(node.right);
        return;
    }
}

PreOrder 방식으로 순회하였고, 시간복잡도는 O(n) 이 됩니다. O(n)보다 더 개선시키려면 이진 트리의 완전성을 이용하여 노드 수를 더 빠르게 계산할 수 있습니다. 완전 이진 트리에서 노드의 수는 2^h-1 입니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int CountNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftDepth = depth(root, true);
        int rightDepth = depth(root, false);

        // If the tree has the last level full
        if (leftDepth == rightDepth) {
            return (1 << leftDepth) - 1;
        } else { // If the tree does not have the last level full
            return CountNodes(root.left) + CountNodes(root.right) + 1;
        }
    }

    private int depth(TreeNode node, bool left) {
        int d = 0;
        while (node != null) {
            d++;
            node = left ? node.left : node.right;
        }
        return d;
    }
}

왼쪽 서브트리와 오른쪽 서브트리의 깊이를 각각 계산하여 트리의 완전성을 확인합니다. 만약 두 깊이가 같다면, 트리는 완전하며 노드의 수는 2^d - 1입니다. 그렇지 않다면, 왼쪽 서브트리와 오른쪽 서브트리의 노드 수를 각각 재귀적으로 계산하고, 루트 노드를 포함하기 위해 1을 더합니다. 이 방법을 사용하면, 모든 노드를 방문하지 않아도 노드 수를 계산할 수 있습니다. 이는 시간 복잡도를 개선하는 데 도움이 됩니다.