[LeetCode] 222. Count Complete Tree Nodes / JAVA

문제설명

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

Count Complete Tree Nodes - LeetCode

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

 

complete binary tree의 노드 수를 반환하세요.

문제에서 complete binary tree란, 마지막 level을 제외하고 모든 노드가 채워진 binary tree를 의미합니다. 그리고 마지막 level은 가능한 왼쪽에 있습니다.

 

아이디어

1. 마지막 노드를 찾아서 1 + 2^h + 마지막 level의 노드 수를 계산한다.

2. 모든 노드를 방문해서 수를 센다.

2번이 간단하여 2번으로 해결했습니다.

 

Solution

/**
 * 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 {
    int nodeCnt = 0;
    private int searchTree(TreeNode treeNode){
        nodeCnt++;
        if(treeNode.left != null){
            nodeCnt = searchTree(treeNode.left);
        } else {
            return nodeCnt;
        }
        if(treeNode.right != null){
            nodeCnt = searchTree(treeNode.right);
        }
        return nodeCnt;
    }

    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        return searchTree(root);
    }
}

Result