一键生成logo免费网站,.net 响应式网站,网站建设与管理考试,网络运营的岗位职责及任职要求1. 题目
给出一个完全二叉树#xff0c;求出该树的节点个数。
说明#xff1a; 完全二叉树的定义如下#xff1a;在完全二叉树中#xff0c;除了最底层节点可能没填满外#xff0c;其余每层节点数都达到最大值#xff0c;并且最下面一层的节点都集中在该层最左边的若干…1. 题目
给出一个完全二叉树求出该树的节点个数。
说明 完全二叉树的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2h 个节点。
示例:
输入: 1/ \2 3/ \ /
4 5 6输出: 6来源力扣LeetCode 链接https://leetcode-cn.com/problems/count-complete-tree-nodes 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
通用办法遍历即可
class Solution {int count 0;
public:int countNodes(TreeNode* root) {if(root NULL)return 0;count;countNodes(root-left);countNodes(root-right);return count;}
};计算包含当前节点在内的左屋檐和右屋檐高度相等的话说明是完全二叉树直接公式计算不相等的话递归调用
class Solution {int h, hL, hR;
public:int countNodes(TreeNode* root) {if(root NULL)return 0;hL leftHeight(root);hR rightHeight(root);if(hL hR)return (1hL)-1;//或者 pow(2,hL)-1;else//hL hRreturn 1countNodes(root-left)countNodes(root-right);}int leftHeight(TreeNode* root){for(h 0 ; root; rootroot-left)h;return h;}int rightHeight(TreeNode* root){for(h 0 ; root; rootroot-right)h;return h;}
};计算某节点的左子的左屋檐 右子的左屋檐左边 右边说明左边是完全的直接公式左边 右边说明右边是完全的直接公式
class Solution {int h, hL, hR;
public:int countNodes(TreeNode* root) {if(root NULL)return 0;hL Height(root-left);hR Height(root-right);if(hL hR)return (1hL)countNodes(root-right);else//hL hRreturn (1hR)countNodes(root-left);}int Height(TreeNode* root){for(h 0 ; root; rootroot-left)h;return h;}
};
