力扣-222题完全二叉树的节点个数（C++）- 迭代+递归+完全二叉树的性质

我会带着你远行 2022-09-02 12:57 113阅读 0赞

题目链接：[https://leetcode-cn.com/problems/count-complete-tree-nodes/][https_leetcode-cn.com_problems_count-complete-tree-nodes]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]  
解法一：迭代

/**
     * 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) {
        
            int result=0;
            if(root==NULL) return result;
            
            queue<TreeNode*> que;
            que.push(root);
    
            while(!que.empty()){
        
                int size=que.size();
                result+=size;
                
                while(size--){
        
                    TreeNode* node=que.front();
                    que.pop();
    
                    if(node->left) que.push(node->left);
                    if(node->right) que.push(node->right);
                }
            }
    
            return result;
        }
    };

解法二：递归

解法三：完全二叉树的性质

/**
     * 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==NULL) return 0;
            TreeNode* left=root->left;
            TreeNode* right=root->right;
            int L_length=0,R_length=0;
    
            while(left){
        
                left=left->left;
                L_length++;
            }
    
            while(right){
        
                right=right->right;
                R_length++;
            }
    
            if(L_length==R_length){
        
                return (2<<L_length)-1;//2<<1 即2^2,
            }
    
            return countNodes(root->left)+countNodes(root->right)+1;
        }
    };

[https_leetcode-cn.com_problems_count-complete-tree-nodes]: https://leetcode-cn.com/problems/count-complete-tree-nodes/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/4169b512517e41dabd18a361cf93bb7f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20220829/7c8f915e215445c9b834f8eeca2e275c.png