家庭宽带做网站服务器吗,房地产集团网站模板,怎样用云服务器做网站,旅游网网站建设的管理题目描述
给你一棵 完全二叉树 的根节点root #xff0c;求出该树的节点个数。
完全二叉树的定义如下#xff1a;在完全二叉树中#xff0c;除了最底层节点可能没填满外#xff0c;其余每层节点数都达到最大值#xff0c;并且最下面一层的节点都集中在该层最左边的若干位…题目描述
给你一棵 完全二叉树 的根节点root 求出该树的节点个数。
完全二叉树的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2h 个节点。
题目分析
迭代法
简单暴力直接上层次遍历万能的层次遍历
/*** Definition for a binary tree node.* 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) {// 层次遍历queueTreeNode* q;if(root!NULL) q.push(root);int num 0; // 节点个数numwhile(!q.empty()){int size q.size();while(size--){ // 遍历每层节点TreeNode* node q.front();q.pop();num;// 放入该节点下层的左右孩子if(node-left) q.push(node-left);if(node-right) q.push(node-right);}}return num;}
};递归法
递归计算左右子树的结点个数然后合并。
class Solution {
public:int countNodes(TreeNode* root) {// 递归遍历每一层都在计算子树的节点数量// 递归终止条件if(rootNULL) return 0;int left countNodes(root-left);int right countNodes(root-right);int total left right 1;return total;}
};不过这题有个特殊条件完全二叉树。完全二叉树有两种情况一种是满二叉树另一种是最后一层叶子节点不是满的。我们知道满二叉树的节点数是很好计算的也就是 2 n − 1 2^n-1 2n−1 n n n是深度。那么我们可以利用递归计算寻找到的满二叉树的节点数量一层一层传上来就得到了整体完全二叉树的节点数量。
class Solution {
public:int countNodes(TreeNode* root) {// 递归法// 递归终止条件if(rootNULL) return 0;TreeNode* left root-left;TreeNode* right root-right;int leftDepth 0, rightDepth 0;while(left) {left left-left;leftDepth;}while(right){right right-right;rightDepth;}if(leftDepthrightDepth){ // 判断当前子树是不是满二叉树即左右深度相同// 如果是满二叉树则返回节点个数return (2 leftDepth) - 1;}// 单层递归逻辑return countNodes(root-left) countNodes(root-right) 1;}
};
