为什么这个算法的运行时间是 O(t)？

Question

这是Cracking the Coding Interview第6版的第4.8题。以下代码是以下提示的一种解决方案："Find the first common ancestor of two nodes in a binary tree"

TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){
/* Checks if either node is not in the tree, or if one covers the other. */
   if(!covers(root, p) || !covers(root, q)){
      return null;
   } else if (covers(p,q)){
      return p;
   } else if (cover(q,p)){
      return q;
   }

   /* Traverse upwards until you find a node that covers q. */
   TreeNode sibling = getSibling(p);
   TreeNode parent = p.parent;
   while(!covers(sibling, q)){
    sibling = getSibling(parent);
    parent = parent.parent;
   }

   return parent;
}

boolean covers(TreeNode root, TreeNode p){
   if(node == null) return false;
   if(root == p) return true;
   return covers(root.left, p) || covers(root.right,p);
}

TreeNode getSibling(TreeNode node){
   if(node == null || node.parent ==null){
     return null;
   }

   TreeNode parent = node.parent;
   return parent.left == node ? parent.right: parent.left;

}

书上说"this algorithm takes O(t) time, where t is the size of the subtree for the first common ancestor. In the worst case this will be O(n)"

但是，在 commonAncestor 开始时从根调用 covers 不是使运行时间为 O(d+t)，d 是 p 或 q 的深度，具体取决于哪个更深。

Answer 1

嗯，看起来 cover(root,p) 将搜索以 x 为根的整个 sub-tree，因为它会递归地检查 root.left 和 root.right。

但是是的，这个问题可以在时间 O(d) 内解决。（从每个 p、q 向上到根，然后是两个列表共有的第一个元素。）

嗯，看起来 cover 中的代码也是错误的，有几个不同的方面：

当我们重复 "off the end" 一个分支时，它可能想要 return false 而不是 return null；
更麻烦的是，偶尔要检查一下是否找到了目标：if (root==p) return true。（聪明的人可以将现有的 return 语句修改为 return (root==p) || covers(..,..) || covers(..,..)。）

Answer 2

您可能想复习本书开头关于 Big O 的部分。 O(d+t) 有点准确，但因为这是其中的一个加号（d 或 t）会比另一个更快地变大。在这种情况下，t = 子树中的节点数，d = 整个树中的深度。 T 的增长速度将明显快于 d。

举例说明：

      1
    /   \
  2       3
 / \     / \
4   5   6   7

If We're looking at this tree and we want to know the common ancestor for 4 and 5:
  t = 3
  d = 3
if we want the common ancestor of 2 and 7 in the same tree then:
  t = 7
  d = 3

由于树的工作方式，深度总是等于或小于节点数。因此，时间复杂度将是 t（子树中的节点数）的平均值（big theta？）和最坏的（大 o）n（树中的节点数）。

顺便说一句，对 root 的检查将在开始时执行 O(n)，这将使整个事情成为 O(n)，但作者指出它确实如此，实际上有 O(n) . "this algorithm takes O(t) time"我认为是作者对一般情况的分析。

为什么这个算法的运行时间是 O(t)？

Why is the runtime of this algorithm O(t)?

java

binary-tree