algorithm - 亚马逊访谈:BST中叶节点的总和

我为此编写的代码：

   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;
     }

我已经通过绘制递归树检查过了，看起来很好，但是我还是有些困惑，我在做一些错误的事情请纠正我我在这里做错了什么。

最佳答案

好吧，看起来你并没有实际添加叶节点的和。
在parcticular中-行：

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中返回它。
但是请注意，递归将转到每个叶-它只是缺少从每个叶返回值。

关于algorithm - 亚马逊访谈:BST中叶节点的总和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12953961/