LeetCode 222.完全二叉树的节点个数

LeetCode 222.完全二叉树的节点个数

引用

CSDN

1.

https://m.blog.csdn.net/weixin_50878507/article/details/143139512

题目描述

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

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

示例 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. 确定递归函数的参数和返回值。参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。
2. 确定终止条件。如果为空节点的话，就返回0，表示节点数为0。
3. 确定单层递归的逻辑。先求左子树的节点数量，再求右子树的节点数量，最后取总和再加一（加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。

时间复杂度：O(n)

迭代法

只需要稍微改动一下模版，将变量result用于统计节点数量即可。

时间复杂度：O(n)

按照完全二叉树的特性来求解：

递归法

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

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用2^树深度 - 1来计算，注意这里根节点深度为1。

对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？

在完全二叉树中，如果递归向左外遍历的深度等于递归向右外遍历的深度，那说明就是满二叉树，否则不是满二叉树。

本方法的巧妙之处在于计算左外侧深度（一直往左）和右外侧深度（一直往右）时，中间的节点是不需要遍历的，这样就节省了时间，而且能够直接使用满二叉树的公式来计算节点数量。

终止条件：

• 如果为空节点的话，就返回0，表示节点数为0。
• 如果是满二叉树的话，就返回满二叉树的节点数：2^树深度 - 1。

代码

C++版：
方法一：递归法（后序遍历）

/**
 * 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 dfs(TreeNode* node){
        if(node==NULL) return 0;
        int leftNum=dfs(node->left); // 左
        int rightNum=dfs(node->left); // 右
        int sum=1+leftNum+rightNum; // 中
        return sum;
    }
    int countNodes(TreeNode* root) {
        return dfs(root);
    }
};

方法二：迭代法（层序遍历）

/**
 * 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) {
        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;
    }
};

方法三：按照完全二叉树的特性来求解

/**
 * 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 dfs(TreeNode* node){
        // 终止条件
        if(node==NULL) return 0;
        TreeNode* left=node->left;
        TreeNode* right=node->right;
        int leftHeight=0;
        int rightHeight=0;
        // 统计左侧深度
        while(left){
            left=left->left;
            leftHeight++;
        }
        // 统计右侧深度
        while(right){
            right=right->right;
            rightHeight++;
        }
        // 另外一个终止条件：遇到满二叉树
        if(leftHeight==rightHeight){
            // 位运算，向左移leftHeight位，相当于2的(leftHeight+1)次方
            return (2<<leftHeight)-1;
        }
        int leftNum = dfs(node->left); // 左
        int rightNum = dfs(node->right); // 右
        int sum = leftNum + rightNum + 1; // 中
        return sum;
    }
    int countNodes(TreeNode* root) {
        return dfs(root);
    }
};

Python版：
方法一：递归法（后序遍历）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # 递归法，后序遍历
    def getNodesNum(self, cur):
        if not cur:
            return 0
        leftNum = self.getNodesNum(cur.left) #左
        rightNum = self.getNodesNum(cur.right) #右
        treeNum = leftNum + rightNum + 1 #中
        return treeNum
    def countNodes(self, root: Optional[TreeNode]) -> int:
        return self.getNodesNum(root)

方法二：迭代法（层序遍历）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # 迭代法，层序遍历
    def countNodes(self, root: Optional[TreeNode]) -> int:
        queue = collections.deque()
        if root:
            queue.append(root)
        result = 0
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                result += 1 #记录节点数量
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result

方法三：按照完全二叉树的特性来求解

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # 递归法，利用完全二叉树的特性，后序遍历
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left = root.left
        right = root.right
        leftHeight = 0 
        rightHeight = 0
        while left: #求左子树深度
            left = left.left
            leftHeight += 1
        while right: #求右子树深度
            right = right.right
            rightHeight += 1
        if leftHeight == rightHeight:
            return (2 << leftHeight) - 1 
        return self.countNodes(root.left) + self.countNodes(root.right) + 1

需要注意的地方

1. leftHeight和rightHeight初始化为0是为了能够让下面求指数变得方便（可以使用位运算），如果不使用位运算的话应初始化为1。