本文主要是介绍NC 完全二叉树结点数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
系列文章目录
文章目录
- 系列文章目录
- 前言
前言
前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你的码吧。
描述
给定一棵完全二叉树的头节点head,返回这棵树的节点个数。
完全二叉树指:设二叉树的深度为h,则 [1,h-1] 层的节点数都满足个
class Solution {
public:int nodeNum(struct TreeNode* head) {if (!head) return 0; // 空树算0个// 计算左右孩子, 不用判空, 如果left或right为空, 函数返回0int lh = getHeight(head->left), rh = getHeight(head->right);int res = 1; // 根节点算1个if (lh == rh) {// (1<<lh) - 1 是左子树满二叉树的节点数, 右子树一定也是完全二叉树, 故递归计算res += nodeNum(head->right) + (1<<lh) - 1;} else {// 同上, 右子树一定是满二叉树res += nodeNum(head->left) + (1<<rh) - 1;}return res;}int getHeight(struct TreeNode* head) {int h = 0; // 初始高度是0while (head) {h++; // 当前节点存在, 高度加1head = head->left; // 向左走}return h;}
};
这篇关于NC 完全二叉树结点数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!