222. 完全二叉树的节点个数
题意:
给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。
完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
示例 1:
输入:root = [1,2,3,4,5,6]
输出:6
示例 2:
输入:root = []
输出:0
示例 3:
输入:root = [1]
输出:1
解题思路:
第一种: 递归
利用递归.终止条件就是遇到就放回0.不是
nullptr
就加1;
nullptr
代码:
if (!root)
return 0; //是nullptr就放回
return countNodes(root->left) + countNodes(root->right) + 1; //不是就继续,自己+1
第二种: 迭代
遍历全部节点,用count记录结点数即可.无论什么遍历都可以.我这里用的是前序遍历
int count = 0;
stack<TreeNode *> stk;
stk.push(root);
while (!stk.empty())
{
TreeNode *node = stk.top();
stk.pop();
count++;
if (node->right)
stk.push(node->right);
if(node->left)
stk.push(node->left);
}
return count;
总结:
f(node->left)
stk.push(node->left);
}
return count;
#### 总结:
> 我运行时结果的时间和空间一样的,所以熟悉那种做法就用那种即可.