222 Count Complete Tree Nodes 完全二叉樹的節點個數

給出一個完全二叉樹，求出該樹的節點個數。

完全二叉樹的定義如下：

在完全二叉樹中，除了最底層節點可能沒填滿外，其餘每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若幹位置。若最底層為第 h 層，則該層包含1~ 2h 個節點。

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

Java實作：

分别找出以目前節點為根節點的左子樹和右子樹的高度并對比，如果相等，則說明是滿二叉樹，直接傳回節點個數，如果不相等，則節點個數為左子樹的節點個數加上右子樹的節點個數再加1(根節點)，其中左右子樹節點個數的計算可以使用遞歸來計算。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        int hl=0;
        int hr=0;
        TreeNode left=root;
        TreeNode right=root;
        while(left!=null){
            ++hl;
            left=left.left;
        }
        while(right!=null){
            ++hr;
            right=right.right;
        }
        if(hl==hr){
            return (int)(Math.pow(2,hl)-1);
        }
        return 1+countNodes(root.left)+countNodes(root.right);
    }
}      

C++實作：

/**
 * 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) {
        if(root==nullptr)
        {
            return 0;
        }
        int hl=0,hr=0;
        TreeNode* left=root,*right=root;
        while(left)
        {
            ++hl;
            left=left->left;
        }
        while(right)
        {
            ++hr;
            right=right->right;
        }
        if(hl==hr)
        {
            return pow(2,hl)-1;
        }
        return 1+countNodes(root->left)+countNodes(root->right);
    }
};