mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
31 lines
1.4 KiB
Markdown
31 lines
1.4 KiB
Markdown
# [222. Count Complete Tree Nodes](https://leetcode.com/problems/count-complete-tree-nodes/)
|
||
# 思路
|
||
计算一颗完全二叉树的节点个数. 先来看看完全二叉树的定义:
|
||
> 对于一颗二叉树，假设其深度为d（d>1）。除了第d层(即最底层)外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，
|
||
这样的二叉树被称为完全二叉树；
|
||
|
||
我们首先考虑如果这颗完全二叉树最后一层也是满的(这样的二叉树叫完美二叉树), 那节点数就好求了, 直接是2^d - 1, 那如何判断最后一层是否是满的呢?
|
||
我们只需要分别向左和向右下降, 若两种方式得到的深度是相等的则说明最后一层是满的, 这棵树是完美二叉树, 此时直接返回节点数.
|
||
|
||
那么如果不是完美的呢? 此时, 我们可以考虑递归计算其左右子树的节点数, 因为其左右子树总有一颗是完美的.
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int countNodes(TreeNode* root) {
|
||
if(!root) return 0;
|
||
TreeNode *left = root, *right = root;
|
||
int right_high = 0;
|
||
while(right){
|
||
right = right -> right;
|
||
left = left -> left;
|
||
right_high++;
|
||
}
|
||
if(!left) return pow(2, right_high) - 1;
|
||
|
||
return countNodes(root -> left) + countNodes(root -> right) + 1;
|
||
}
|
||
};
|
||
```
|