Count Complete Tree Nodes
LeetCode 222 完全二叉树节点个数：利用完全二叉树性质做递归优化。
#resource / algorithm
#type / howto
#status / evergreen
#ds / tree
#algo / recursion
#source / leetcode
[!info] related notes 算法面试题型 MOC 二叉树高频题
Count Complete Tree Nodes
LeetCode: https://leetcode.cn/problems/count-complete-tree-nodes/
思路
完全二叉树的性质：
- 如果某子树是“满二叉树”（perfect tree），节点数可以直接用
2^h - 1得到。 - 对当前节点
cur：比较cur.right的最左路径高度是否能到达整棵树的高度。- 如果能到达：说明左子树是满的，直接加上左子树节点数，再递归右子树。
- 否则：说明右子树是满的，直接加上右子树节点数，再递归左子树。
这样能把复杂度降到 O((log n)^2)。
Java Template
class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
int h = mostLeftLevel(root, 1);
return count(root, 1, h);
}
// cur: current node
// level: cur is at this level
// h: total height of the tree
private int count(TreeNode cur, int level, int h) {
if (level == h) return 1;
// if right subtree's leftmost level reaches height h,
// left subtree is perfect
if (mostLeftLevel(cur.right, level + 1) == h) {
// left perfect nodes: 2^(h-level) - 1, plus current node => 2^(h-level)
return (1 << (h - level)) + count(cur.right, level + 1, h);
} else {
// right perfect nodes: 2^(h-level-1) - 1, plus current node => 2^(h-level-1)
return (1 << (h - level - 1)) + count(cur.left, level + 1, h);
}
}
// returns the deepest level reachable by going left from cur
private int mostLeftLevel(TreeNode cur, int level) {
while (cur != null) {
level++;
cur = cur.left;
}
return level - 1;
}
}