leetcode 222 完全二叉树的节点个数

浅浅的花香味﹌ 2022-09-11 12:25 13阅读 0赞

## 前言 ##

题目：[222.完全二叉树的节点个数][222.]

参考题解：[完全二叉树的节点个数-代码随想录][-]

--------------------

## 提交代码 ##

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

方法一：深度遍历或者广度遍历的过程中，记录节点个数。

方法二：使用递归，充分利用完全二叉树的性质。如果当前树是完全二叉树，树节点个数为`2^(h-1)-1`。如果当前树不是完全二叉树，树节点个数为`1+左子树节点个数+右子树节点个数`。时间复杂度最差为 O ( l o g n ∗ l o g n ) O(logn\*logn) O(logn∗logn)，最好为 O ( l o g n ) O(logn) O(logn)

class Solution {
    public:
        int countNodes(TreeNode* root) {
            // 如果当前树是完全二叉树。树节点个数：2^(h-1)-1
            // 如果当前树不是完全二叉树。树节点个数：1+左子树节点个数+右子树节点个数
            if(root == nullptr) 
                return 0;
            
            int leftDepth = 0; // 左子树高度
            int rightDepth = 0; // 右子树高度
            TreeNode* leftNode = root->left;
            TreeNode* rightNode = root->right;
    
            while(leftNode != nullptr){
                leftDepth++;
                leftNode = leftNode->left;
            }
    
            while(rightNode != nullptr){
                rightDepth++;
                rightNode = rightNode->right;
            }
    
            if(leftDepth == rightDepth){ //以root为根节点的树为满二叉树
                return (2<<(leftDepth+1-1))-1;
            }else{
                return 1 + countNodes(root->left) + countNodes(root->right);
            }
    
        }
    };

[222.]: https://leetcode-cn.com/problems/count-complete-tree-nodes/
[-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.md