章娅萝 发表于 2025-6-8 22:04:31

算法day13——二叉树（3）

目录


[*]完全二叉树的节点个数
[*]平衡二叉树110
[*]二叉树的所有路径257
[*]左叶子之和404
一、完全二叉树的节点个数

 https://leetcode.cn/problems/count-complete-tree-nodes/description/?envType=problem-list-v2&envId=8At1GmaZ

 　方法一：用普适的递归方法来做，这样会遍历到每一个节点。没有利用完全二叉树的性质。
class Solution {
    public int countNodes(TreeNode root) {
      if(root == null){
            return 0;
      }
      return countNodes(root.left) + countNodes(root.right) + 1;
    }
}
//时间复杂度：O（n）　　方法二：充分利用了“完全二叉树”的结构，避免了重复计算完整子树的节点个数，大大减少了递归次数，因此时间复杂度从 O(n) 降低到了 O((log n)^2)，在大数据量时性能优势明显。

[*]完全二叉树的特点是：左子树深度等于右子树深度 ⇒ 整个左子树是满二叉树，节点数是 2^depth - 1。
[*]利用这一性质，可以直接跳过对整棵子树的递归计算，用位运算直接得出节点数。
class Solution {    public int countNodes(TreeNode root) {      if(root == null){            return 0;      }      int left = countLevel(root.left);      int right = countLevel(root.right);      if(left == right){            return countNodes(root.right) + (1

归悦可 发表于 2025-10-26 00:45:56

分享、互助 让互联网精神温暖你我

纣捎牟 发表于 2025-11-1 17:17:58

前排留名，哈哈哈

裴涛 发表于 2025-11-26 16:58:32

不错，里面软件多更新就更好了

喳谍 发表于 2025-12-7 13:38:27

不错，里面软件多更新就更好了

距佰溘 发表于 2025-12-14 03:40:52

谢谢分享，试用一下

袁可佳 发表于 2025-12-18 08:33:17

感谢分享，学习下。

少屠 发表于 2026-1-13 03:31:36

不错，里面软件多更新就更好了

户烫擞 发表于 2026-1-15 02:20:20

谢谢分享，辛苦了

阴昭昭 发表于 2026-1-18 16:01:20

这个好，看起来很实用

卜笑 发表于 2026-1-19 01:35:15

谢谢分享，辛苦了

叟澡帅 发表于 2026-1-20 20:54:02

分享、互助 让互联网精神温暖你我

管水芸 发表于 2026-1-21 13:03:06

感谢分享，下载保存了，貌似很强大

瞧厨 发表于 2026-1-24 08:05:23

懂技术并乐意极积无私分享的人越来越少。珍惜

抽厉 发表于 2026-1-24 14:17:48

谢谢分享，试用一下

骆贵 发表于 2026-1-29 08:32:55

感谢分享，下载保存了，貌似很强大

氛疵 发表于 2026-1-30 00:02:39

懂技术并乐意极积无私分享的人越来越少。珍惜

诘琅 发表于 2026-1-30 05:09:59

收藏一下   不知道什么时候能用到

贼瘁 发表于 2026-1-31 15:25:02

热心回复！

庇床铍 发表于 2026-2-5 05:18:31

收藏一下   不知道什么时候能用到
页: [1] 2
查看完整版本: 算法day13——二叉树（3）