完全二叉树的计算结点总数算法

Question

/**

• 定义二叉树的结点如下
• struct TreeNode {
• int val;
• struct TreeNode *left;
• struct TreeNode *right;
• }; / 算法如下： int countNodes(struct TreeNode root) { if(root==NULL)//如果传进一棵空树 return 0; if(root->left==NULL)//如果传进一棵只有根结点的树木 return 1; if(root->right==NULL)//如果这颗树就只有一颗子树 return 2; return (countNodes(root->left)+countNodes(root->right)+1); } 该算法在OJ上面判断出错，说是算法时间超出限制，求解，这个算法错在哪里。

Answer 1

int countNodes(struct TreeNode *root)
{

if(root!=NULL)
{
  if(root->left==NULL&&root->right==NULL)//叶子节点
      return 1;
  else //其中至少一个子树不为空，那就意味着可能有多个节点。
      //总节点数是左子树节点数+右子树节点数+1（自身节点）
      return countNodes(root->left)+countNodes(root->right)+1;

}else//如果为空，则说明不存在这个节点，故返回零。
    return 0;

}

您的算法有缺陷的，如楼上所述。
if(root->left==NULL)//如果传进一棵只有根结点的树木 return 1; if(root->right==NULL)//如果这颗树就只有一颗子树 return 2;

这两个if语句是不妥的。