首页 > 其他分享 >15_完全二叉树的节点个数

15_完全二叉树的节点个数

时间:2023-12-06 10:15:46浏览次数:32  
标签:right 15 int 二叉树 root 节点 left

完全二叉树的节点个数

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

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

示例 1:

img

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

示例 2:

输入:root = []
输出:0

示例 3:

输入:root = [1]
输出:1

提示:

  • 树中节点的数目范围是[0, 5 * 104]
  • 0 <= Node.val <= 5 * 104
  • 题目数据保证输入的树是 完全二叉树

法一:递归法

1、确定递归函数的参数返回值:参数就是传入树的根节点返回就返回以该节点为根节点二叉树的节点数量,所以返回值为int类型。

int getNodesNum(TreeNode root)

2、确定终止条件:如果为空节点的话,就返回0,表示节点数为0。

if (cur == null)  return 0;

3、确定单层递归的逻辑:先求它的左子树的节点数量,再求右子树的节点数量,最后取总和再加一(加1是因为算上当前中间节点)就是目前节点为根节点的节点数量。

int leftNum = getNodesNum(cur.left);    //左
int rightNum = getNodesNum(cur.right);  //右
int treeNum = leftNum + rightNum + 1;   //中

时间复杂度:O(n)

空间复杂度:O(logn),算上了递归系统栈占用的空间

class Solution {
	//通用递归解法
	public int countNodes(TreeNode root) {
		if (root == null) {
			return 0;
		}
		return 1 + countNode(root.left) + countNode(root.right);
	}
}

法二:迭代法

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null)  return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int count = 1;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            while (levelSize-- > 0) {
                TreeNode temp = queue.poll();
                if (temp.left != null) {
                    queue.add(temp.left);
                    count++;
                }

                if (temp.right != null) {
                    queue.add(temp.right);
                    count++;
                }
            }
        }
        return count;
    }
}

法三:完全二叉树的特性

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

class Solution {
	/
        针对完全二叉树的解法,满二叉树的节点数为:2^depth - 1
    */
    public int countNodes(TreeNode root) {
        if (root == null)  return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0, rightDepth = 0;//这里初始化为0是有目的的,为了下面求指数方便
        while (left != null) {  //求左子树的深度
            left = left.left;
            leftDepth++;
        }
        while (right != null) {
            right = right.right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1;  // 注意(2<<1) 相当于2^2,所以leftDepth初始为0
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

标签:right,15,int,二叉树,root,节点,left
From: https://www.cnblogs.com/codingbao/p/17878877.html

相关文章

  • leetcode-1572-easy
    MatrixDiagonalSumGivenasquarematrixmat,returnthesumofthematrixdiagonals.Onlyincludethesumofalltheelementsontheprimarydiagonalandalltheelementsonthesecondarydiagonalthatarenotpartoftheprimarydiagonal.Example1:......
  • leetcode-1550-easy
    ThreeConsecutiveOddsGivenanintegerarrayarr,returntrueiftherearethreeconsecutiveoddnumbersinthearray.Otherwise,returnfalse.Example1:Input:arr=[2,6,4,1]Output:falseExplanation:Therearenothreeconsecutiveodds.Example2:......
  • leetcode-1512-easy
    NumberofGoodPairsGivenanarrayofintegersnums,returnthenumberofgoodpairs.Apair(i,j)iscalledgoodifnums[i]==nums[j]andi<j.Example1:Input:nums=[1,2,3,1,1,3]Output:4Explanation:Thereare4goodpairs(0,3),(0,4),(......
  • Linux_315_Ansible模块之定时任务管理
    ansible的cron模块来添加任务1、添加定时任务,每5分钟进行时间同步ansibleyu-mcron-a"name=ntp_cronjob='/usr/sbin/ntpdatentp.aliyun.com>/dev/null2>&1'minute=*/5"2、远程的查看定时任务是否添加ansibleyu-mshell-a"crontab-l"3、再添加一个记录,事件是......
  • day15 函数复习和模块基础
    蒙特卡洛仿真2023-12-0519:28:40函数复习deffunc(*args,**kwargs): pass#func可以接受所有的参数*形参:接受多余的位置实参以元组的形式存储**形参:接受多余的关键字参数以字典的形式存储函数对象的作用:①引用f1=func②作为函数的返回值returnfunc③作为函数的参数f2(......
  • 代码随想录算法训练营第六天| 454.四数相加 15.三数之和 18.四数之和
    LeetCode454.四数相加题目链接:LeetCode454思路: 将两个数组中的数存放到一个map中,用另外两个数组的值在map中去减 classSolution{public:intfourSumCount(vector<int>&A,vector<int>&B,vector<int>&C,vector<int>&D){unordered_map&l......
  • 文心一言 VS 讯飞星火 VS chatgpt (150)-- 算法导论12.2 6题
    六、用go语言,考虑一棵二叉搜索树T,其关键字互不相同。证明:如果T中一个结点x的右子树为空,且x有一个后继y,那么y一定是x的最底层祖先,并且其左孩子也是x的祖先。(注意到,每个结点都是它自己的祖先。)文心一言,代码正常运行:灵捷3.5。为了证明上述命题,我们需要定义几个......
  • 文心一言 VS 讯飞星火 VS chatgpt (150)-- 算法导论12.2 6题
    六、用go语言,考虑一棵二叉搜索树T,其关键字互不相同。证明:如果T中一个结点x的右子树为空,且x有一个后继y,那么y一定是x的最底层祖先,并且其左孩子也是x的祖先。(注意到,每个结点都是它自己的祖先。)文心一言,代码正常运行:灵捷3.5。为了证明上述命题,我们需要定义几个辅助......
  • Educational Codeforces Round 159 总结
    最失败的一集。C开题顺序搞错,不小心先开了C,以为是A。还好C不难。题意大概是在给定的数组最后添一个数(所有数两两不同),再自定义一个数\(k\),数组中每个数可以加上若干个\(k\),最后使得所有数字相等。要求加\(k\)的次数最少。如果不加最后一个数,那么显然把所有的数加到与最大......
  • GMK15100-ASEMI光伏设备二极管GMK15100
    编辑:llGMK15100-ASEMI光伏设备二极管GMK15100型号:GMK15100品牌:ASEMI正向电流:15A反向耐压:100V封装:批号:2023+引脚数量:2工作温度:-55°C~150°CGMK15100特征:肖特基势垒高二极管;热阻低;正向压降低,功率损耗低隔离包装设计,非常适合散热;高正向电流能力;优异的抗湿性;低调的......