Daily LeetCode Challenge - 222. Count Complete Tree Nodes

Problem From.
https://leetcode.com/problems/count-complete-tree-nodes/

오늘 문제는 Complete Tree Node 에서 총 노드의 갯수를 구하는 문제였다.
완전이진트리 (complete Tree Node) 는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있어야 한다.
문제를 O(n) 의 실행시간안에 풀어야하는 제약 조건이 있었는데, 제약조건을 실현시키기 위해 간단한 방법을 썼다.

주어진 트리가 완전이진트리이기 때문에 노드의 왼쪽 맨 끝과 노드의 오른쪽 맨 끝의 깊이가 같다면 트리는 빈공간이 없이 꽉 채워져 있기 때문에 깊이의 제곱을 한 다음 두 번 세어진 루트를 하나 빼면 답이 나온다.

만약 깊이가 다르다면 각각의 노드를 재귀호출하여 이진트리속의 노드의 갯수를 세면 된다.

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun countNodes(root: TreeNode?): Int {
        
        root ?: return 0
        
        var left = root
        var right = root
        var leftCnt = 0
        var rightCnt = 0
        
        while(left != null) {
            leftCnt += 1
            left = left.left
        }
        
        while(right != null) {
            rightCnt += 1
            right = right.right
        }
        
        if(leftCnt == rightCnt) return Math.pow(2.0, leftCnt.toDouble()).toInt() - 1
        return 1 + countNodes(root.left) + countNodes(root.right)
        
    }
}

위 방법의 실행시간은 O(logn) * O(logn) 이 된다.