leetcode【二叉树—中等】222.完全二叉树的节点个数

文章目录

• 前言
• 题目
• 题解
• NO1：递归统计
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为二叉树专题。

---

题目

题目来源leetcode

leetcode地址：222. 完全二叉树的节点个数，难度：中等。

题目描述(摘自leetcode)：

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

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

示例 2：
输入：root = []
输出：0

示例 3：
输入：root = [1]
输出：1
 
提示：
树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树

本地调试代码：

class Solution {

    //迭代遍历
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

}

class Main {
    public static void main(String[] args) {
        // 构建树
        Integer[] nums = new Integer[] {1};
        TreeNode root = buildTree(nums);
        System.out.println(new Solution().countNodes(root));
    }

    //根据数组来构建二叉树
    public static TreeNode buildTree(Integer[] nums) {
        if(nums == null || nums.length == 0){
            return null;
        }
        Deque<TreeNode> queue = new LinkedList();
        TreeNode root = new TreeNode(nums[0]);
        queue.add(root);
        for (int i = 1; i < nums.length; i += 2) {
            TreeNode parentNode = queue.poll();
            if (nums[i] != null) {
                TreeNode leftNode = new TreeNode(nums[i]);
                queue.offer(leftNode);
                parentNode.left = leftNode;
            } else {
                parentNode.left = null;
            }
            if (i + 1 < nums.length && nums[i + 1] != null) {
                TreeNode rightNode = new TreeNode(nums[i+1]);
                queue.offer(rightNode);
                parentNode.right = rightNode;
            } else {
                parentNode.right = null;
            }
        }
        return root;
    }

}

---

题解

NO1：递归统计

思路： 就是一个递归遍历，最终不断合并左右子节点的数量，最终得到节点个数。

代码：

class Solution {

    //迭代遍历
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

}

---

参考文章

[1]. leetcode题解

[2]. 代码随想录—完全二叉树的节点个数

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.9