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