#|【Leetcode二叉树属性四】222. 完全二叉树的节点个数 leetcode|算法|数据结构|二叉树

文章目录

Leetcode222
- 1.问题描述
- 2.解决方案
- - 解法一：普通二叉树递归
  - 解法二：普通二叉树迭代
  - 解法三：利用完全二叉树性质递归
  - - 思路：
    - 代码实现：

Leetcode222 1.问题描述

文章图片

文章图片

2.解决方案

解法一：普通二叉树递归

就左右子树加起来再加一

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

解法二：普通二叉树迭代

就是层序遍历然后计数一下最后return这个计数器就好

解法三：利用完全二叉树性质递归
思路：

思路就是遇到满二叉树了直接使用公式返回

【#|【Leetcode二叉树属性四】222. 完全二叉树的节点个数】

文章图片

代码实现：

1.在判断满二叉树的时候利用了完全二叉树的性质，一个left->left，一个right->right，由于我们知道完全二叉树的性质，即使不是满二叉树最后一层的结点也只会集中在左边，所以right->right这样求出来的高度如果等于left那就必定是满二叉树了
2.代码实现的时候其实就是遇到一个root我们先判断它是不是满二叉树如果是直接返回公式return (2<left)+ countNodes(root->right)递归下去

class Solution1 {public: int countNodes(TreeNode* root) {if(root== nullptr) return 0; //1.如果root是完全二叉树 TreeNode* left=root->left; TreeNode* right=root->right; int leftHeight=0; int rightHeight=0; while(left!= nullptr){left=left->left; leftHeight++; } while(right!= nullptr){right=right->right; rightHeight++; } if(leftHeight==rightHeight) return (2<left)+ countNodes(root->right); } };