从零开始的LeetCode刷题日记：222. 完全二叉树的节点个数

一.相关链接

题目链接：222. 完全二叉树的节点个数

二.心得体会

这道题可以用暴力方法直接计算节点。但可以利用到完全二叉树的特点，只要判断出此题里一棵树的最左和最右节点的深度一样就说明是一颗完全二叉树。

三.代码

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == NULL) return 0;
        int leftNodeNumber=0;
        int rightNodeNumber=0;
        TreeNode* leftNode = root->left;
        TreeNode* rightNode = root->right;
        while(leftNode) {
            leftNode = leftNode->left; //判断最左节点深度
            leftNodeNumber++;
        }
        while(rightNode) {
            rightNode = rightNode->right;//判断最右节点深度
            rightNodeNumber++;
        }
        //相等的话就说明是完全二叉树，用公式进行计算，省去遍历树中间的节点的步骤
        if(leftNodeNumber == rightNodeNumber) return pow(2, leftNodeNumber + 1) - 1;
        //不是的话就老老实实递归
        int leftNumber = countNodes(root->left);
        int rightNumber = countNodes(root->right);
        return leftNumber + rightNumber + 1;
    }
};

原文地址：https://blog.csdn.net/chenjialehhh/article/details/143078974

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！