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;

和一个过长的指令

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

面试官总是喜欢被问到他们给出的问题。诸如“是否给出了 BST 或者我可以设计一个针对给定叶子总和进行优化的结构？”、“BST 有多大？”之类的问题......可以添加一个加号，并且很可能会完全改变您的答案。

于 2012-10-18T12:05:23.557 回答