代码如下1.迭代法:前序遍历:
class Solution {
public int countNodes(TreeNode root) {
if(root==null)
{
return 0;
}
int n=0;
Stack stack =new Stack<>();
stack.push(root);
while(!stack.isEmpty())
{
TreeNode node=stack.pop();
n++;
if(node.right!=null)
{
stack.push(node.right);
}
if(node.left!=null)
{
stack.push(node.left);
}
}
return n;
}
}
递归法:
class Solution {
public int generate(TreeNode root)
{
if(root==null)
{
return 0;
}
int leftnum=generate(root.left);
int rightnum=generate(root.right);
return leftnum+rightnum+1;
}
public int countNodes(TreeNode root) {
return generate(root);
}
}
完全二叉树的解法:
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其实是 (2^leftDepth - 1) + 1 ,左子树 + 根结点
return (1 << leftDepth) + countNodes(root.right);
} else {// 右子树是满二叉树
return (1 << rightDepth) + countNodes(root.left);
}
}
private int getDepth(TreeNode root) {
int depth = 0;
while (root != null) {
root = root.left;
depth++;
}
return depth;
}
}



