###### tags: `Leetcode` `medium` `tree` `python` `c++`

# 222. Count Complete Tree Nodes

## [題目連結:] 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.


## 解題想法:
* 題目為求complete tree的node總數
* complete binary tree完全二元樹: 最後一層節點樹不滿
* Full binary tree完全二元樹: 最後一層滿的
* 先求左右子樹高:
* 樹高函式getHeight:
* 一律只往左子樹遞迴計算
* 若左樹高==右樹高:
* 則表示左子全滿，右子可能滿or只是complete tree
* 總數=2 ** 左樹高 +遞迴右子
* 若高度不相等:
* 表示左子樹較高(可能為全滿or complete tree)，右子樹較矮(全滿)
* 總數=2 ** 右樹高 +遞迴左子

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root = self
        que=[root]
        res=[]
        while que:
            curRoot=que.pop(0)
            res.append(curRoot.val)
            if curRoot.left:
                que.append(curRoot.left)
            if curRoot.right:
                que.append(curRoot.right)
        print(res)
        
class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        #time O(logN * logN)
        if not root:
            return 0
        nodes = 0
        left_height = self.getHeight(root.left)
        right_height = self.getHeight(root.right)
        if left_height==right_height: #若相等 則左子全滿 右子可能滿or只是complete tree
            nodes = 2**left_height + self.countNodes(root.right)
        else: #右子差左子一整層
            nodes = 2**right_height + self.countNodes(root.left)
        return nodes
        
    def getHeight(self,root): #起始根節點高度視為0
        height=0
        tmp=root
        while tmp:
            height+=1
            tmp=tmp.left
        return height

root = TreeNode(1)
root.insertLeft(2)
root.insertRight(3)
root.left.insertLeft(4)
root.left.insertRight(5)
#root.right.insertLeft(6)
root.printTree()

result = Solution()
ans = result.countNodes(root)
print(ans)

## C++:

/**
 * 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==nullptr)
            return 0;
        int nodes=0;
        int leftHeight=getHeight(root->left);
        int rightHeight=getHeight(root->right);
        if (leftHeight==rightHeight) //#include <cmath>
            nodes=pow(2,leftHeight)+countNodes(root->right);
        else
            nodes=pow(2,rightHeight)+countNodes(root->left);
        return nodes;
    }

    int getHeight(TreeNode* root){
        int height=0;
        TreeNode* tmp=root;
        while (tmp){
            tmp=tmp->left;
            height+=1;
        }
        return height;
    }
};