LeetCode 222. 完全二叉树的节点个数（二分查找）

Michael阿明

发布于 2020-07-13 16:07:45

5620

发布于 2020-07-13 16:07:45

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

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 (1<<hL)-1;//或者 pow(2,hL)-1;
        else//hL > hR
        	return 1+countNodes(root->left)+countNodes(root->right);
    }

    int leftHeight(TreeNode* root)
    {
    	for(h = 0 ; root; root=root->left)
    		++h;
    	return h;
    }

    int rightHeight(TreeNode* root)
    {
    	for(h = 0 ; root; root=root->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 (1<<hL)+countNodes(root->right);
        else//hL > hR
        	return (1<<hR)+countNodes(root->left);
    }

    int Height(TreeNode* root)
    {
    	for(h = 0 ; root; root=root->left)
    		++h;
    	return h;
    }
};