Count Complete Tree Nodes[Binary Search,Bit Manipulation,Tree,Binary Tree]

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

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 * 104].
• 0 <= Node.val <= 5 * 104
• The tree is guaranteed to be complete.

분노의 Binary Search 한 번 더..

 

1. C++

Binary를 어떻게 이용하라는 거지? 걍 container로 풀어버렸다..

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        vector<TreeNode*> vec;
        // how could solve it by Binary Search..
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* temp = q.front();
            q.pop();
            if(find(vec.begin(),vec.end(),temp)==vec.end()){
                vec.push_back(temp);
            }
            if(temp->left) q.push(temp->left);
            if(temp->right) q.push(temp->right);
        }
        return vec.size();
    }
};

 

2. C 졸지에 Recursion;;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int countNodes(struct TreeNode* root) {
    if(!root) return 0;
    return countNodes(root->left) + countNodes(root->right) + 1;
}

 

3. Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:

    def countNodes(self, root: Optional[TreeNode]) -> int:
        
        def helper(node) -> int :
            if not node : return 0
            else :
                return helper(node.left) + helper(node.right) + 1

        return helper(root)