C++算法练习-day32——222.完全二叉树的节点个数

题目来源：. - 力扣（LeetCode）

题目思路分析

给定一棵二叉树，我们的目标是计算其节点总数。直接遍历所有节点并计数的方法虽然简单，但在最坏情况下（树完全不平衡）的时间复杂度为O(n)，其中n是节点总数。为了优化这个计算过程，我们可以利用二叉树的性质。特别是，如果一棵二叉树的左子树和右子树深度相同，那么这棵树就是一个满二叉树（或完全二叉树的一个子集），其节点总数可以直接通过数学公式计算得出。如果左右子树深度不同，我们则分别递归计算左右子树的节点数，然后求和并加上根节点。

代码:

/**  
 * 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) {  
        // 如果当前节点为空，则返回0，表示没有节点  
        if(!root){  
            return 0;  
        }  
          
        // 初始化左子树和右子树的深度为0  
        int l_depth = 0, r_depth = 0;  
          
        // 计算左子树的深度  
        TreeNode* node = root;  
        while(node->left){  
            ++l_depth;  
            node = node->left;  
        }  
          
        // 重置node到根节点，计算右子树的深度  
        node = root;  
        while(node->right){  
            ++r_depth;  
            node = node->right;  
        }  
          
        // 如果左子树和右子树的深度相同，说明当前树是满二叉树  
        // 使用公式2^(深度+1) - 1计算满二叉树的节点总数  
        if(l_depth == r_depth){  
            return pow(2, l_depth + 1) - 1;  
        }  
        else{  
            // 如果左右子树深度不同，则分别递归计算左右子树的节点数  
            // 然后将这两个值相加，并加上当前节点（root），得到整棵树的节点总数  
            return countNodes(root->left) + countNodes(root->right) + 1;  
        }  
    }  
};

注释详解：

• if(!root){return 0;}：如果当前节点为空，则返回0，表示没有节点。
• int l_depth = 0, r_depth = 0;：初始化左子树和右子树的深度为0。
• TreeNode* node = root;：临时节点，用于遍历子树以计算深度。
• while(node->left){...}：计算左子树的深度。
• node = root;：重置临时节点到根节点，用于计算右子树的深度。
• while(node->right){...}：计算右子树的深度。
• if(l_depth == r_depth){...}：如果左右子树深度相同，计算满二叉树的节点总数。
• else{...}：如果左右子树深度不同，递归计算左右子树的节点数并求和。

知识点摘要

• 二叉树的基本概念：二叉树是一种树形数据结构，其中每个节点最多有两个子节点，称为左子节点和右子节点。
• 满二叉树：一棵二叉树，如果除了叶子节点外的每个节点都有两个子节点，则称为满二叉树。
• 递归：递归是一种在函数内部调用函数自身的编程技巧，常用于解决可以分解为相似子问题的问题。
• 深度优先搜索（DFS）：深度优先搜索是一种用于遍历或搜索树或图的算法，它尽可能深地搜索树的分支。

在本文中，我们介绍了一种高效计算二叉树节点总数的方法。通过判断左右子树的深度是否相同，我们可以确定当前树是否为满二叉树，并直接计算其节点总数。如果左右子树深度不同，则递归计算左右子树的节点数并求和。这种方法结合了数学计算和递归，相比直接遍历所有节点的方法，能够显著提高计算效率。通过本文的学习，读者可以掌握这种优化技巧，并在实际编程中加以应用。