Given acompletebinary tree, count the number of nodes.
Definition of a complete binary tree from:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftMostHeight = getHeight(root, true);
int rightMostHeight = getHeight(root, false);
if (leftMostHeight == rightMostHeight) {
return (1 << leftMostHeight) - 1;
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
public int getHeight(TreeNode node, boolean isLeft) {
int height = 0;
while (node != null) {
if (isLeft) {
node = node.left;
}
else {
node = node.right;
}
++height;
}
return height;
}
}
(2) Method 2: 二分法
思路：根据Complete tree的leaf node as far left as possible的特点，对一个节点的左子树和右子树，我们分别找出最左的深度。如两边最左深度相同，说明左子树是完美二叉树，可以直接用公式计算node个数，否则右边子树的高度肯定小于左边子树，而且右边子树根据complete的特点也必然是完美二叉树，用公式计算其node个个数。这样就可以达到二分的效果
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int count = 1;
int leftHeight = getLeftMostHeight(root.left);
int rightHeight = getLeftMostHeight(root.right);
if (leftHeight == rightHeight) {
count += (1 << leftHeight) - 1;
count += countNodes(root.right);
}
else {
count += (1 << rightHeight) - 1;
count += countNodes(root.left);
}
return count;
}
public int getLeftMostHeight(TreeNode node) {
int height = 0;
while (node != null) {
node = node.left;
++height;
}
return height;
}
}