Leetcode 完全二叉树的节点个数
不讲武德的解法
java 实现
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
根据完全二叉树和满二叉树的性质做
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
if (leftDepth == rightDepth) {
// 左子树是满二叉树，节点数为 2^leftDepth - 1，加上根节点和右子树
return (1 << leftDepth) + countNodes(root.right);
} else {
// 右子树是满二叉树，节点数为 2^rightDepth - 1，加上根节点和左子树
return (1 << rightDepth) + countNodes(root.left);
}
}
private int getDepth(TreeNode node) {
int depth = 0;
while (node != null) {
depth++;
node = node.left; // 完全二叉树的最左路径
}
return depth;
}
}