博客

给你一棵

完全二叉树

的根节点root，求出该树的节点个数。


完全二叉树

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

^h

个节点。

满二叉树

的定义如下：二叉树除了叶结点外所有节点都有两个子节点。是

完全二叉树

的特例。

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

输出：6

思路一：层序遍历递归

1. 递归法

class Solution {
private:
	int getNodeNum(TreeNode* cur) {
		if (cur == 0) return 0;
		int leftNum = getNodesNum(cur->left); // 左
		int rightNum = getNodesNum(cur->right); // 右
		int treeNum = leftNum + rightNum + 1; // 中
		return treeNum;
	}
public:
	int countNodes(TreeNode* root)
	{
		return getNodeNum(root);
	}
};

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(logn)，递归系统栈占用的空间

2. 迭代法

class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        int result = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                result++;   // 记录节点数量
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

思路二：完全二叉树

完全二叉树只有两种情况：

• case1：满二叉树
• case2：最后一层叶子节点没有满

1. 对于case1，可以直接用2
   
   ^树深度-1
   
   来计算，根节点深度为1
2. 对于case2，分别递归左孩子和右孩子，递归到某一深度，一定会有左孩子或者右孩子为满二叉树。

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftHeight = 0, rightHeight = 0; // 这里初始为0是有目的的，为了下面求指数方便
        while (left) {  // 求左子树深度
            left = left->left;
            leftHeight++;
        }
        while (right) { // 求右子树深度
            right = right->right;
            rightHeight++;
        }
        if (leftHeight == rightHeight) {
            return (2 << leftHeight) - 1; // 注意(2<<1) 相当于2^2，所以leftHeight初始为0
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

时间复杂度：O(logn * logn)

空间复杂度：O(logn)