不讲武德的解法
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;}
}