【代码随想录day 15】 力扣 222.完全二叉树的节点个数

视频讲解：https://www.bilibili.com/video/BV1eW4y1B7pD/?vd_source=a935eaede74a204ec74fd041b917810c
文档讲解：https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html
力扣题目：https://leetcode.cn/problems/count-complete-tree-nodes/description/

计算二叉树的节点个数涉及到两种情况，一种情况是普通二叉树，我们使用遍历的方法来计算节点个数；另一种情况是完全二叉树，我们可以通过判断哪里开始时完全二叉树，再通过完全二叉树计算公式2^(深度)-1来直接计算节点个数，这可以大大减小计算开销。
判断是否是完全二叉树的方法：遍历左右两边子树深度，如果两边子树深度相等则证明他是完全二叉树。

class Solution {
public:int countNodes(TreeNode* root) {//如果根节点为空，直接返回0if(root==NULL) return 0;TreeNode *left=root->left;TreeNode *right=root->right;//初始化左右深度int leftDepth = 0,rightDepth=0;//一直往左节点遍历while(left){left=left->left;leftDepth++;}//一直往右节点遍历while(right){right=right->right;rightDepth++;}//如果左右深度相等说明他是完全二叉树，我们使用公式计算if(leftDepth==rightDepth){return (2 << leftDepth) - 1; }int leftresult=countNodes(root->left);int rightresult=countNodes(root->right);int result=leftresult+rightresult+1;return result;}
};