C++ 解法, 执行用时: 1ms, 内存消耗: 384KB, 提交时间: 2017-08-24

/**
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    int nodeNum(struct TreeNode* root) {
		if (root == nullptr) {
            return 0;
        }
        return bs_node_num(root, 1, left_level(root, 1));
    }
    int bs_node_num(TreeNode *head, int l, int h) {
        if (l == h) {
            return 1;
        }
        if (left_level(head->right, l + 1) == h) {
            return (1 << (h - l)) + bs_node_num(head->right, l + 1, h);
        }
        else {
            return (1 << (h - l - 1)) + bs_node_num(head->left, l + 1, h);
        }
    }
    int left_level(TreeNode *head, int level) {
        while (head) {
            ++level;
            head = head->left;
        }
        return level - 1;
    }

};

C++ 解法, 执行用时: 2ms, 内存消耗: 364KB, 提交时间: 2021-06-03

/**
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
//     int nodeNum(TreeNode* root) {
//         if (root == nullptr) {
//             return 0;
//         }
//         int level = 0;
//         TreeNode* node = root;
//         while (node->left != nullptr) {
//             level++;
//             node = node->left;
//         }
//         int low = 1 << level, high = (1 << (level + 1)) - 1;
//         while (low < high) {
//             int mid = (high - low + 1) / 2 + low;
//             if (exists(root, level, mid)) {
//                 low = mid;
//             } else {
//                 high = mid - 1;
//             }
//         }
//         return low;
//     }

//     bool exists(TreeNode* root, int level, int k) {
//         int bits = 1 << (level - 1);
//         TreeNode* node = root;
//         while (node != nullptr && bits > 0) {
//             if (!(bits & k)) {
//                 node = node->left;
//             } else {
//                 node = node->right;
//             }
//             bits >>= 1;
//         }
//         return node != nullptr;
//     }
    
    int nodeNum(struct TreeNode* head) {
        if(!head) return 0;
        //return calcNode(head);
        TreeNode *node = head;
        int level = 0;
        while(node->left)
        {
            ++level;
            node = node->left;
        }
        int low = 1 << level, high = (1 << (level + 1)) - 1;
        while(low < high)
        {
            int mid = (high - low + 1) / 2 + low;
            if(isExist(head, level, mid))
            {
                low = mid;
            }
            else
            {
                high = mid - 1;
            }
        }
        return low;
    }
    
    bool isExist(TreeNode *root, int level, int target)
    {
        int bits = 1 << (level - 1);
        TreeNode *node = root;
        while(node && bits > 0)
        {
            if((target & bits) == 0)//(target & bits)要加括号！！！！
            {
                node = node->left;
            }
            else
            {
                node = node->right;
            }
            bits >>= 1;
        }
        if(node)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
//     int calcNode(TreeNode *head)
//     {
//         int lLen = 0, rLen = 0;
//         TreeNode *cur = head;
//         while(cur)
//         {
//             ++lLen;
//             cur = cur->left;
//         }
//         cur = head;
//         while(cur)
//         {
//             ++rLen;
//             cur = cur->right;
//         }
        
//         if(lLen == rLen)
//         {
//             return (1 << lLen) - 1;
//         }
//         else
//         {
//             return 1 + calcNode(head->left) + calcNode(head->right);
//         }
        
//     }
    
};

C++ 解法, 执行用时: 2ms, 内存消耗: 364KB, 提交时间: 2021-03-05

/**
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    int nodeNum(struct TreeNode* head) {
        if(head==nullptr) return 0;
        
        int llen = 0;
        TreeNode *left = head->left;
        while(left){
            llen++;
            left = left->left;
        }
        int rlen = 0;
        TreeNode *right = head->right;
        while(right){
            rlen++;
            right = right->right;
        }
        if(llen == rlen){
//              if(llen == 0) return 1;
            return (1<<(llen+1)) - 1;
            
        }
        
        return 1 + nodeNum(head->left) + nodeNum(head->right);
        
        
        
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 364KB, 提交时间: 2020-12-14

/**
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    int res = 0;
    int nodeNum(struct TreeNode* head) {
        search(head);
        return res;
    }
    void search(TreeNode* head){
        if (head) {
            res++;
            nodeNum(head->left);
            nodeNum(head->right);
        }
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-05-29

class Solution {
public:
    int nodeNum(struct TreeNode *head) {
        if (!head) {
            return 0;
        }

        int leftHeight = 1, rightHeight = 1;
        struct TreeNode *left = head->left, *right = head->right;
        while (left) {
            ++leftHeight;
            left = left->left;
        }
        while (right) {
            ++rightHeight;
            right = right->right;
        }
        if (leftHeight == rightHeight) {
            return pow(2, leftHeight) - 1;
        }

        return 1 + nodeNum(head->left) + nodeNum(head->right);
    }
};