222. Count Complete Tree Nodes

1.問題

• 給予一個complete binary tree, 計算node數量

2.想法

• complete binary tree: 左右子樹的高度差在1以內, 每個leaf不一定有兩個child, 但會先填左子樹

• full binary tree: 左右子樹的高度差沒有限制, 每個leaf一定有兩個child

• perfect binary tree: 左右子樹的高度差在1以內, 每個leaf一定有兩個child,

3.程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        int left = findLeftDepth(root);
        int right = findRightDepth(root);
        if (left == right) {
            return pow(2, left) - 1;
        } 
        
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
private:
    int findLeftDepth(TreeNode* root) {
        if (!root) {
            return 0;
        }
        
        return findLeftDepth(root->left) + 1;
    }
    
    int findRightDepth(TreeNode* root) {
        if (!root) {
            return 0;
        }
        
        return findRightDepth(root->right) + 1;
    }
};