博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
完全二叉树节点个数
阅读量:6793 次
发布时间:2019-06-26

本文共 1853 字,大约阅读时间需要 6 分钟。

A Complete Binary Tree (CBT) is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;

换句话说,完全二叉树从根结点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子结点都靠左对齐。

A Perfect Binary Tree(PBT) is a tree with all leaf nodes at the same depth. All internal nodes have degree 2.

二叉树的第i层至多拥有2^{i-1}个节点数;深度为k的二叉树至多总共有{\displaystyle 2^{\begin{aligned}k+1\end{aligned}}-1}个节点数,而总计拥有节点数匹配的,称为“满二叉树”;

A Full Binary Tree (FBT) is a tree in which every node other than the leaves has two children.

换句话说,所有非叶子结点的度都是2。(只要你有孩子,你就必然是有两个孩子。)

 

通过上面的定义,我们可以看出二者的关系是,完美二叉树一定是完全二叉树,而完全二叉树不一定是完美二叉树。那么这道题给的完全二叉树就有可能是完美二叉树,若是完美二叉树,节点个数很好求,为2的h次方-1,h为该完美二叉树的高度。这道题可以用递归和非递归两种方法来解。我们先来看递归的方法,思路是分别找出以当前节点为根节点的左子树和右子树的高度并对比,如果相等,则说明是满二叉树,直接返回节点个数,如果不相等,则节点个数为左子树的节点个数加上右子树的节点个数再加1(根节点),其中左右子树节点个数的计算可以使用递归来计算,参见代码如下:

 

class Solution {public:    int countNodes(TreeNode* root) {        int hLeft = 0, hRight = 0;        TreeNode *pLeft = root, *pRight = root;        while (pLeft) {            ++hLeft;            pLeft = pLeft->left;        }        while (pRight) {            ++hRight;            pRight = pRight->right;        }        if (hLeft == hRight) return pow(2, hLeft) - 1;        return countNodes(root->left) + countNodes(root->right) + 1;    }};
//递归解释class Solution {public:    int countNodes(TreeNode* root) {        int hLeft = leftHeight(root);        int hRight = rightHeight(root);        if (hLeft == hRight) return pow(2, hLeft) - 1;        return countNodes(root->left) + countNodes(root->right) + 1;    }    int leftHeight(TreeNode* root) {        if (!root) return 0;        return 1 + leftHeight(root->left);    }    int rightHeight(TreeNode* root) {        if (!root) return 0;        return 1 + rightHeight(root->right);    }};

 

转载于:https://www.cnblogs.com/springcloud/p/8244224.html

你可能感兴趣的文章
全球首个NB-IoT智慧路灯项目落地鹰潭
查看>>
黑客向苹果勒索高额赎金:否则远程擦除用户iPhone数据
查看>>
南宁:“数字城管”让智慧城市建设提质提速
查看>>
关于用飞信框架运行net程序-用批处理运行
查看>>
微软开始善后 发布补丁告别Win10免费升级
查看>>
类的生命周期回顾篇
查看>>
看全球云IT基础设施供应商的新变化!
查看>>
MES与ERP如何分工合作?
查看>>
物联网纳入电信网编号计划 商用临近产业链蓄势待发
查看>>
VoIP:戴着枷锁的舞者
查看>>
谈谈我理解的软件测试的核心价值
查看>>
数据中心布线:节能又省钱
查看>>
嵌入云端:12c Policy-Managed Cluster为Oracle DBaaS助力
查看>>
Bouygues公司投资1.05亿美元在都柏林建设数据中心
查看>>
电脑开机到操作系统开始启动过程描述
查看>>
适时兴起失势衰落,短视频鼻祖Vine“命悬一线”
查看>>
云存储服务使用八大热点问题
查看>>
为数字化转型护航 网络信息安全需要“内外”兼顾
查看>>
巴西能源部长促进分布式光伏发电发展
查看>>
《vSphere性能设计:性能密集场景下CPU、内存、存储及网络的最佳设计实践》一1.6 了解设计要素...
查看>>