0

私がこれのために書いたコード：

   sumBST(BST *root)
     {
         static sum =0;
         if (root!= null)
           {
              if (root->left != null || root->right != null)
                {
                  sum = sum + sumBST(root->left) + sumBST(root->right);
                  return sum;
                }
              else
                {
                   root->data;
                }
           }
         else
            {
               return 0;
            }
        return sum;
     }

再帰ツリーを描いて確認したのは良さそうですが、それでもある時点で混乱してしまい、ミスをしてしまいました。私がここで何か間違ったことをしているのを訂正してください。

4

2 に答える 2

1

さて、実際にリーフノードの合計を追加しているようには見えません。
特に-行：

root->data

実際にデータを返すのではなく、読み取るだけです。擬似コードでは次のようになります。

sumBST(node):
    if (root == null):
       return 0
    else if (root->left == null && root->right == null)  
       //add the value of the node if it is a leaf, this step is missing
      return root->data;
    else:
      return sumBST(root->left) + sumBST(root->right)

編集：
コードの問題は次のとおりです（回答のその点をさらに明確にして説明します）：

葉のデータをどこかに返す必要があります-これはコードのどこにも発生していません-で返したいと思いますroot->data。

ただし、再帰はすべての葉に適用されることに注意してください。それぞれから値を返すことが欠落しているだけです。

于 2012-10-18T11:55:35.940 に答える
1

このような質問の目的は、主に候補者の思考プロセスを評価することに焦点を当てています。

ここに表示されるのはタイプミスだけです

root->data => return root->data

そして届かない指示

return sum;

と 1 つの過度に長い命令

 sum = sum + sumBST(root->left) + sumBST(root->right); => return sumBST(root->left) + sumBST(root->right);

インタビュアーは常に、自分が与えた問題について質問されることを好みます。「BST は与えられていますか、それとも与えられた葉の合計に対して最適化された構造を設計できますか?」、「BST の大きさは?」などの質問は、プラスを追加して、おそらくあなたの答えを完全に変えることができます。

于 2012-10-18T12:05:23.557 に答える