力扣算法 Java 刷题笔记【二叉树篇】hot100（十一）如何计算完全二叉树的节点数 及其时间复杂度分析 3_java 完全二叉树时间复杂度

1. 普通二叉树节点个数

地址: https://labuladong.gitee.io/algo/2/18/31/
2021/12/15
做题反思：

int countNodes(TreeNode root){
	if (root == null) {
		return 0;
	}
	return countNodes(root.left) + countNodes(root.right) + 1;
}
1
2
3
4
5
6

时间复杂度 O(N)：

2. 满二叉树节点个数

地址: https://labuladong.gitee.io/algo/2/18/31/
2021/12/15
做题反思：

public int countNodes(TreeNode root) {
	int h = 0;
	while (root != null) {
		root = root.left;
		h++;
	}
	return (int)Math.pow(2, h) - 1;
}
1
2
3
4
5
6
7
8

3. 完全二叉树的节点个数

地址: https://leetcode-cn.com/problems/count-complete-tree-nodes/
2021/12/15
做题反思：两个小问题

1. = 和 ==
2. if 和 while

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        TreeNode l = root, r = root;
        int lh = 0, rh = 0;
        while (l != null) {
            l = l.left;
            lh++;
        }
        while (r != null) {
            r = r.right;
            rh++;
        }
        if (rh == lh) {
            return (int)Math.pow(2, lh) - 1;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这个算法的时间复杂度是 O(logN*logN)