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

Question

这是来自《破解编码面试》第 6 版的问题 4.8。以下代码是以下提示的一种解决方案:“查找二叉树中两个节点的第一个共同祖先”

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;

}

书上说“这个算法需要 O(t) 时间，其中 t 是第一个共同祖先的子树的大小。在最坏的情况下，这将是 O(n)”

但是，在 commonAncestor 开始时从 root 开始调用 cover 是否会导致运行时间 O(d+t)，d 是 p 或 q 的深度，具体取决于哪个更深。

Answer 1

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

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

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

• 当我们在分支的“末尾”重复出现时，它可能想要返回 false 而不是返回 null；
• 更麻烦的是，它偶尔应该检查是否找到了目标:if (root==p) return true。 (一个人可以聪明一点，将现有的 return 语句修改为 return (root==p) ||covers(..,..) ||covers(..,..) 。)