计算完全二叉树的节点个数-爱代码爱编程
题目链接
222. 完全二叉树的节点个数 - 力扣(LeetCode)
题目描述
解题思路
这个题目其实是一个简单题目,无论是什么样的二叉树,只要进行遍历,计算数量还是非常简单的。但之所以会有一个满二叉树的的前提,是因为满二叉树的计算可能会有一些神略的遍历。
解题代码
C++
#include<iostream>
#include<cmath>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
int countNodes(TreeNode* root) {
if (root==NULL){
return 0;
}
else{
int leftLen = getLeft(root);
int rightLen = getRight(root);
if (leftLen==rightLen){
return pow(2, leftLen) - 1;
}else{
return 1 + countNodes(root->left) + countNodes(root->right);
}
}
}
int getLeft(TreeNode* root){
TreeNode *p = root;
int res = 0;
while (p != nullptr)
{
res++;
p = p->left;
}
return res;
}
int getRight(TreeNode* root){
TreeNode *p = root;
int res = 0;
while (p != nullptr)
{
res++;
p = p->right;
}
return res;
}
};
JAVA
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int countNodes(TreeNode root) {
if (root==null){
return 0;
}
TreeNode t = root;
int l = 0,r=0;
while (t!=null){
t = t.left;
l++;
}
t = root;
while (t!=null){
t= t.right;
r++;
}
if (l==r){
return (int) (Math.pow(2,l)-1);
}else {
return 1+countNodes(root.left)+countNodes(root.right);
}
}
}
但事实上,不考虑那么多,只算二叉树节点的个数,也能通过
class Solution {
public int countNodes(TreeNode root) {
if (root==null){
return 0;
}
return countNodes(root.left)+countNodes(root.right)+1;
}
}