Problem:
Given a complete binary tree, count the number of nodes.
Java Code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = countLeftHeight(root);
int rightHeight = countRightHeight(root);
if (leftHeight == rightHeight) {
return (int)Math.pow(2, leftHeight + 1) - 1;//Attn: Mistake ^ operator as power here.
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
private int countLeftHeight(TreeNode root) {
if (root == null) {
return -1;
}
return 1 + countLeftHeight(root.left);
}
private int countRightHeight(TreeNode root) {
if (root == null) {
return -1;
}
return 1 + countRightHeight(root.right);
}
}
没有评论:
发表评论