[leetcode #222] Count Complete Tree Nodes

Problem

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.
Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints:

・ The number of nodes in the tree is in the range [0, 5 * 10⁴].
・ 0 <= Node.val <= 5 * 10⁴
・ The tree is guaranteed to be complete.

Idea

これは完全ツリーのノード数を計算する問題です.ツリー内を簡単にナビゲートしてノード数を計算するだけで問題を簡単に解くことができるが,完全なツリーであるため平均時間複雑度はO(n)より低い.完了ツリーでは、ナビゲーション時に左側のサブノードのみのノードを検索するか、兄弟ノードが見つかりますが、深さが異なるノードを見つけたときにすぐにノードの数を取得できます.すなわち、サブノードをブラウズする際に、そのノードに指定された数字で個数を取得することができる.
このように解くと結果はいいと思いますが、実際には1ミリ秒かけて他の人がどのように解いたのかを確定しました.
0ミリ秒の解を生成するには、次のようにします.ノードを参照するたびに、左側のサブツリーの深さと右側のサブツリーの深さを比較します.2つの深さが同じ場合、左側のサブツリーはfull treeであるため、右側のサブツリーをナビゲートし、左側のサブツリーの深さを左にシフトした値をノード数に追加します.depthが異なる場合、右側のサブツリーはフルツリーであるため、左側のサブツリーをナビゲートし、右側のサブツリーのdepthが右に移動した値をノード数に追加します.このプロセスを繰り返すと,ノードの個数を容易に求めることができる.

Solution

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
    
        return traverseTree(root, 0, 0, 1);
    }

    private int traverseTree(TreeNode node, int depth, int maxDepth, int num) {
        if (depth > maxDepth)
            maxDepth = depth;
        if (node.left == null && node.right == null) {
            if (maxDepth != depth)
                return 2 * num - 1;
            else
                return num;
        }
        if (node.left != null & node.right == null)
            return 2 * num;
    
        int left = traverseTree(node.left, depth+1, maxDepth, num*2);
        int right = traverseTree(node.right, depth+1, maxDepth, num*2+1);
    
        return Math.max(left, right);
    }
}

上のコードは私が作ったコードで、下のようにもっといいです.

class Solution {
    public int countNodes(TreeNode root) {
        // Base case
        if(root == null) return 0;
    
        // Get the leftDepth of left subtree and right subtree to check which one is unfull tree
        int left = leftDepth(root.left);
        int right = leftDepth(root.right);
    
        if(left == right) {
            // Left subtree is a full tree, and right subtree could be a non-full tree
            return (1 << left) + countNodes(root.right);
        
        } else {
            // Right subtree is a full tree, and left subtree could be a non-full tree
            return countNodes(root.left) + (1 << right);
        }
    }

    private int leftDepth(TreeNode root) {
        int ans = 0;
    
        while(root != null) {
            ans++;
            root = root.left;
        }
    
        return ans;
    }
}

Reference

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