在BST时间复杂度中查找sum=0的三元组，代码如下

Question

我编写了以下代码，用于在BST中查找相加为0的三元组。但很难确定时间复杂度。

find（）方法的时间复杂度为O（logn）。isTriplet（）的时间复杂度是O（n^2）吗？

bool find(Node* root, int target) {
  if (root == NULL)
      return false;

  if (root->data == target)
      return true;

  return (target < root->data) ?  find(root->left, target) :  find(root->right, target);
}

bool isTriplet(Node* root, Node* actualRoot) {
  if (root == NULL)
     return false;

  if (root->left == NULL && root->right == NULL)
      return false;

  int sum = root->data;
  if (root->left)
      sum += root->left->data;
  else if (root->right)
      sum += root->right->data;

  sum = -1 * sum;

  return (find(actualRoot, sum) || isTriplet(root->left, actualRoot) || isTriplet(root->right, actualRoot));
}

Answer 1

sum=0的三元组表示一个节点、一个左子级和一个右子级，三个元素的和等于0。

让我们逻辑思考。从树根开始，我们应该在哪里寻找这样的三胞胎？基本上，如果根是正的，则向左，如果根是负的，则向右。

我们应该什么时候检查是否发现这样的三联体？在三个数字中至少有一个负数和一个正数的情况下。0是一个特例，我将单独处理。

如果找到这样一个和，那么我们应该返回它并停止算法。因此，如果节点不是0，并且没有三元组，那么我们知道要在哪个子树中搜索。如果它是一个三元组，那么我们有一个简单的情况，因为找到了解。如果当前节点为0，则应检查其三元组是否为0。如果不是，那么我们可以停止搜索，因为任何子树都不会包含正数和负数。例外情况是，当前节点为0，而其一个子节点也正好为0。在这种情况下，我们还需要检查该子树。

对于最坏情况，算法的对数复杂度应为基数2。证明：

>

如果还没有找到这样的三元组，并且当前节点不是0，那么我们有一个有趣的子树和一个不有趣的子树。

如果尚未找到此类三元组，且当前节点为0，则：

3.1。它的两个孩子都是0，我们发现了这样一个三胞胎，

3.2. 它的子元素都不是0，因此可以证明不存在这样的三元组，或者

3.3.它的一个子级是0，但另一个不是，在这种情况下，0个子级定义了有趣的子树，另一个子级对非有趣的子树进行deinfes。

由于所有情况要么由于html" target="_blank">解决方案的存在或不存在而导致算法停止，要么将树减半为有趣和非有趣的子树，因此算法在每个级别上遍历单个节点最多，因此其在最坏情况下的复杂性等于树的高度，这是二进制对数。