222 完全二叉树的节点个数

本文最后更新于：2022年4月2日 上午

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

说明：

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

示例:

1
2
3
4
5
6
7
8
输入: 
    1
   / \
  2   3
 / \  /
4  5 6

输出: 6

Solution

参考：《算法小抄》3.4

  • 求普通二叉树 和 求满二叉树 方法的结合，利用完全二叉树的性质简化
  • 注意求左右子树深度的区别
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        lNode, rNode = root, root
        highL, highR = 0,0
        while lNode:
            lNode = lNode.left
            highL += 1
        while rNode:
            rNode = rNode.right
            highR += 1
        if highL==highR:
            return (1<<highL)-1  # pow(2, highL)-1
        
        return 1+ self.countNodes(root.left)+self.countNodes(root.right)
# @lc code=end

cpp

  • 递归法，后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int getNodesNum(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 getNodesNum(root);
    }
};
// @lc code=end
  • 优化后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==nullptr) return 0;
        int highL=0, highR=0;
        TreeNode* lNode=root->left, *rNode=root->right;
        while(lNode){
            lNode = lNode->left;
            highL += 1;
        }
        while(rNode){
            rNode = rNode->right;
            highR += 1;
        }
        if(highL==highR)
            return (1<<highL)-1;
        
        int leftCount = countNodes(root->left);
        int rightCount = countNodes(root->right);
        return leftCount+rightCount+1;
    }
};
  • 迭代法，层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
    }
};