LeetCode222：完全二叉树节点的数量

本文主要是介绍LeetCode222：完全二叉树节点的数量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
给你一棵完全二叉树的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

在这里插入图片描述

解题思路
使用常规二叉树的思想，直接遍历二叉树

代码
递归的两种实现方式

class Solution {
public:int getNodeSum(TreeNode* node, int& sum) {if (node == nullptr) return 0;++sum;getNodeSum(node->left, sum);getNodeSum(node->right, sum);return sum;}int countNodes(TreeNode* root) {int sum = 0;return getNodeSum(root, sum);}
};

class Solution {
public:int getNodeSum(TreeNode* node) {if (node == nullptr) return 0;int l = getNodeSum(node->left);int r = getNodeSum(node->right);int treeNum = 1 + l + r;return treeNum;}int countNodes(TreeNode* root) {return getNodeSum(root);}
};

使用完全二叉树的性质

class Solution {
public:int countNodes(TreeNode* root) {if (root == nullptr) return 0;int leftDepth = 0, rightDepth = 0;TreeNode* left = root->left, * right = root->right;while (left) {leftDepth++;left = left->left;}while (right) {rightDepth++;right = right->right;}//如果为满二叉树if (leftDepth == rightDepth)return (2 << leftDepth) - 1;return countNodes(root->left) + countNodes(root->right) + 1;}
};