Open youngyangyang04 opened 5 months ago
class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
// TreeNode left = root.left; // 1. 完全二叉树
// TreeNode right = root.right;
// int depth1 = 1, depth2 = 1;
// while (left != null) {
// depth1++;
// left = left.left;
// }
// while (right != null) {
// depth2++;
// right = right.right;
// }
// if (depth1 == depth2)
// return (1 << depth1) - 1; // 2. 普通二叉树
return 1 + countNodes(root.left) + countNodes(root.right);
}
}
想请问一下logN * logN的时间复杂度是怎么算出来的呢?我感觉时间上界是每个节点都计算一次是否完全二叉树,总共的时间复杂度是NlogN
https://www.programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html