leetcode 222 完全二叉树的节点个数

/**
 * 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 getNoteNum(TreeNode* cur)
    {
        if(cur==nullptr) return 0;
        int left_num = getNoteNum(cur->left);
        int right_num = getNoteNum(cur->right);
        return 1 + left_num + right_num;
    }
    int countNodes(TreeNode* root) {
        if(root==nullptr) return 0;
        return getNoteNum(root);
    }
};

/**
 * 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 getnodenum(TreeNode* cur)
    {
        if(cur==nullptr) return 0 ;
        TreeNode* left_tree = cur->left , *right_tree = cur->right;
        int left_tree_num=0 , right_tree_num=0;
    //分别结算左右树的深度是否一样，一样则是完全二叉树
        while(left_tree!=nullptr)
        {
            left_tree = left_tree->left;
            left_tree_num++;
        }
        while(right_tree!=nullptr)
        {
            right_tree = right_tree->right;
            right_tree_num++;
        }
        if(left_tree_num == right_tree_num )
        {
            //完全二叉树节点数量的公式是2^（树的高度）-1
            // return (2<<left_tree_num) - 1;
            // left_tree_num是树的深度，要+1
            return  pow(2,left_tree_num+1) - 1; 
        }else
        {
            return 1 + getnodenum(cur->left) + getnodenum(cur->right) ;
        }
    }
    int countNodes(TreeNode* root) {
        if(root ==nullptr) return 0;
        return getnodenum(root);
    }
};

/**
 * 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 result = 0;
    void back_trak(TreeNode* cur)
    {
        if(cur == nullptr ) return;
        result++;
        back_trak(cur->left);
        back_trak(cur->right);
        return;
    }
    int countNodes(TreeNode* root) {
        if(root == nullptr ) return 0;
        back_trak(root);
        return result;
    }
};