算法力扣刷题记录四十四【222.完全二叉树的节点个数】

前言

二叉树篇继续。
记录四十四【222.完全二叉树的节点个数】

一、题目阅读

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例 1：
在这里插入图片描述

输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

提示：

树中节点的数目范围是[0, 5 * 10^4]
0 <= Node.val <= 5 * 10^4
题目数据保证输入的树是 完全二叉树

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

二、尝试实现

思路

（1）统计节点个数：把完全二叉树当成一个普通的树，按照二叉树的遍历，num++ 即可。遍历方式：前中后序；实现：递归和迭代。一共6种，都是通过遍历整个树，顺便统计。如何遍历在【专栏】记录三十五、三十六学习练习过。
（2）但是题目给了完全二叉树。就想用完全二叉树的性质来实现：

通过while循环可以获得完全二叉树的深度。
在最后一层之上，肯定是满的。所以for循环统计了除最后一层之外的节点个数。
那么最后一层该怎么统计？（卡住……）

/**
 * 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) {
        if(!root) return 0;
        int sum = 0;
        int height = 1;
        TreeNode* left = root->left;
        while(left){
            height++;
            left = left->left;
        }
        for(int i = 0;i< height-1;i++){
            sum = sum*2 + 1;
        }
        //统计最后一层
        
    }
};

三、参考学习

参考思路链接

学习内容

方法一：遍历实现

思路：按后序（左右中），求出左子树的节点个数；再求右子树的节点个数；回到中间节点，两边相加后再加1；这个逻辑可以重复传递。所以递归实现，类似这篇求深度。

代码实现：

/**
 * 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 getnum(TreeNode* cur){
        //终止条件
        if(!cur) return 0;
        int leftnum = getnum(cur->left);
        int rightnum  = getnum(cur->right);
        return leftnum+rightnum+1;
    }
    int countNodes(TreeNode* root) {
        return getnum(root);
    }
};

或者：直接在countNodes中递归实现：
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        int leftnum = countNodes(root->left);
        int rightnum = countNodes(root->right);
        return leftnum+rightnum+1;
    }
};

如果前序遍历实现，中序，后序同理：

/**
 * 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 num;
    void traversal(TreeNode* cur){
        if(!cur) return ;
        num++;
        traversal(cur->left);
        traversal(cur->right);
    }
    int countNodes(TreeNode* root) {
        num = 0;
        traversal(root);
        return num ;
    }
};

方法二：利用完全二叉树的性质

思路：完全二叉树除最后一层外，就是满二叉树，和满二叉树有一定联系；满二叉树计算套公式：节点总数是2ⁿ-1，n是深度。

如果左子树是满二叉树，计算出深度，可以利用公式求节点总数；
如果右子树是满二叉树，计算出深度，可以利用公式求节点总数；
如果不是满二叉树，再深入到左（右）子树内部找满二叉树，只要找到满二叉树就可以统一用公式。最后的叶子节点，一定算满二叉树。
所以这就有递归的逻辑。

怎么确定是满二叉树呢？题目说输入是完全二叉树。如果一直left到叶子节点的深度=一直right到叶子节点的深度，说明这是满二叉树。

代码实现：

/**
 * 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 getnum(TreeNode* cur){
    	//如果是空，终止条件
        if(!cur) return 0;
        //求左边深度
        int leftdepth = 1;
        TreeNode* left = cur->left;
        while(left){
            leftdepth++;
            left = left->left;
        }
        //求右边深度
        int rightdepth = 1;
        TreeNode* right = cur->right;
        while(right){
            rightdepth++;
            right= right->right;
        }
        if(leftdepth == rightdepth){    //这是满二叉树，直接得到子树节点总数，不用递归深入。
            return (1<<leftdepth) - 1;//<<是二进制左移运算符
        }
        //不是满二叉树，深入递归。
        int leftnum = getnum(cur->left);
        int rightnum = getnum(cur->right);
        return leftnum+rightnum+1;//返回左子树+右子树+1
    }
    int countNodes(TreeNode* root) {
        return getnum(root);
    }
};