c-完全二叉樹的計算結點總數算法

完全二叉樹的計算結點總數算法

/**

• 定義二叉樹的結點如下
• 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上面判斷出錯，說是算法時間超出限制，求解，這個算法錯在哪裡。

最佳回答：

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語句是不妥的。