2 qq 28653047 qq_28653047 于 2016.05.10 23:17 提问

二叉树的节点数的问题

给出一个完整二叉树,查找结点个数。
假设二叉树结点结构如下:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

请完成此函数:
class Solution
{
public:
int countNodes(TreeNode* root)
{
}
}
请给出该函数的算法复杂度,如O(n)/O(n^2)。

2个回答

caozhy
caozhy   Ds   Rxr 2016.05.11 09:22
 class Solution
{
public:
int countNodes(TreeNode* root)
{
int n = 1;
if (root->left != null)
n += countNodes(root->left);
if (root->right != null)
n += countNodes(root->right;
return n;
}
}

复杂度O(N)
CSDNXIAOD
CSDNXIAOD   2016.05.10 23:22

二叉树的高度和节点数
二叉树的节点个数和深度(非递归)
Catalan数—求解n个节点能组成的二叉树个数问题
----------------------biu~biu~biu~~~在下问答机器人小D,这是我依靠自己的聪明才智给出的答案,如果不正确,你来咬我啊!

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
二叉树-节点数和边数的关系
n0:叶子节点的数量; n1:度为1的节点数量; n2:度为2的节点数量;节点的总数量n = n0 + n1 + n2;边的数量表示1: 边的数量S = n1 + 2 * n2(这个好理解);边的数量表示2: 边的数量S = n - 1; 注:除了根节点,每个节点,都有一条边,指向该节点;推导,叶子节点**n0和度为2节点**n2的关系: n1 + 2 * n2 = n - 1 即,
求二叉树节点数 -- 采用递归和非递归方法
/*求二叉树节点数 -- 采用递归和非递归方法(本例非递归采用先序遍历) 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <stack>using std::cout; using std::cin; using std::endl; using std::stack;/*二叉树结点定义*/ typedef s
二叉树(5)----求二叉树节点数,递归与非递归
1、二叉树定义 typedef struct BTreeNodeElement_t_ { void *data; } BTreeNodeElement_t; typedef struct BTreeNode_t_ { BTreeNodeElement_t *m_pElemt; struct BTreeNode_t_ *m_pLeft; struct BTr
Java学习笔记之二叉树的节点数、深度
在上篇博文《Java学习笔记之创建二叉树》后,我们现在来求增加二叉树的节点数、二叉树的深度的函数,以下代码中黄色背景是增加实现的代码,由于注释较多,我用绿色字体将自己解读的注解区分。 老样子还是先注明这句话:【本文的代码请见原创http://blog.csdn.net/wuwenxiang91322/article/details/12231657】 我是结合他的代码一行行通过注释解读
统计二叉树每层节点个数并打印每层节点
先看百度一道面试题: 有一颗二叉树,定义树的高度为从根到叶子节点的最长距离,树的宽度为每层节点的最大值,树的面积定义为高度和宽度的乘积。写一个函数计算一个二叉树的面积。(15分) 解决这道题参考资料剑指offer和编程之美,分别求求二叉树高度和宽度。 都是采用递归: 求高度参考:http://blog.csdn.net/buyingfei8888/article/details
求二叉树的结点总数
/*求二叉树的结点总数*/ #include<stdio.h> #define maxsize 100 typedef char datatype; /*二叉链表类型定义*/ typedef struct Binnode { datatype data; /*数据域*/ struct BinNode* lchild,*rchild; /*指向左、
7-6 求二叉树中指定层次的节点个数
//求二叉树中指定层次的节点个数 #include &quot;btree.cpp&quot; void Lnodenum(BTNode *b,int h,int k,int &amp;amp;n) { if (b==NULL) //空树直接返回 return; else //处理非空树 { if (h==k) n++; //当前访问的节点在第k层时,n增1 else if (h&amp;lt;k) //...
二叉树定义及相关术语、节点数计算公式、代码实现(遍历,Java版)
二叉树 定义:二叉树是由n(n>=0)个节点组成的有限集,或者为空树(n=0),或者为由一个根节点和两个分别称为左子树和右子树的的互不相交的二叉树构成。 特点:(1).每个节点最多能有两棵子树,即左子树和右子树。              (2).左子树和右子树右次序之分,如  术语: (1)节点的度:一个节点含有的子树的个数。 (2)叶节点:度为零的节点。 (3)非叶节点:度不为零
求一个二叉树每一层节点个数
import java.util.HashMap; import java.util.LinkedList; import java.util.Map; import java.util.Map.Entry; import java.util.Set; public class Test4 { public static void main(String[] args) { ...
计算一棵完整二叉树的结点数 C实现
题目描述 分析 学过图论的我们知道,一棵层数为h的完整二叉树的最大节点数为2^h-1(节点的层数:从根开始定义起,根为第1层,根的子节点为第2层…)。那么问题来了,若结点范围是在2^(h-1)和2^h之间,怎么算呢?一种很直接的方法便是等于左子树的结点数+右子树的节点数+1。至此,我们就大概知道代码怎么写了。如果刚好是满二叉树,那么节点数便是2^h-1;如果不是,那么就左子树、右子树的结点数分别加