最低的共同祖先破解代码采访解决方案

Question

我想了解破解编码采访页面129中的解决方案之一。这是关于找到最低的共同祖先。请参阅下面的代码。我的问题是在评论

总之，我的问题是：

1）这行代码：

if(root.left == p || root.left == q) return root.left; 

为什么返回root.left而不是根？

2）对于这些代码：

else if (nodesFromLeft == ONE_NODE_FOUND) { 
    if (root == p) return p; 
    else if (root == q) return q; 
    } 

为什么回报p如果根== P，这是怎么祖先？同样适用于q。

这里是低于整个代码：

static int TWO_NODES_FOUND = 2; 
static int ONE_NODE_FOUND = 1; 
static int NO_NODES_FOUND = 0; 

// Checks how many “special” nodes are located under this root 
int covers(TreeNode root, TreeNode p, TreeNode q) { 

     int ret = NO_NODES_FOUND; 
     if (root == null) return ret; 
     if (root == p || root == q) ret += 1; 
     ret += covers(root.left, p, q); 
     if(ret == TWO_NODES_FOUND) // Found p and q 
      return ret; 
return ret + covers(root.right, p, q); 
} 

TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
     if (q == p && (root.left == q || root.right == q)) return root; 

     int nodesFromLeft = covers(root.left, p, q); // Check left side 
     if (nodesFromLeft == TWO_NODES_FOUND) { 
      if(root.left == p || root.left == q) return root.left;//Qn1:See above 
     else return commonAncestor(root.left, p, q); 
     } 
     else if (nodesFromLeft == ONE_NODE_FOUND) { 
      if (root == p) return p; //Qn 2: See qn above 
      else if (root == q) return q; //Qn2: See qn above 
     } 
     int nodesFromRight = covers(root.right, p, q); // Check right side 
     if(nodesFromRight == TWO_NODES_FOUND) { 
      if(root.right == p || root.right == q) return root.right; 
     else return commonAncestor(root.right, p, q); 
     } 
     else if (nodesFromRight == ONE_NODE_FOUND) { 
      if (root == p) return p; 
      else if (root == q) return q; 
     } 
     if (nodesFromLeft == ONE_NODE_FOUND && nodesFromRight == ONE_NODE_FOUND) return root; 

     else return null; 
} 

Answer 1

为什么返回root.left而不是根？

当nodesFromLeft是2时，那么两个p和q是root.left下。 如果其中之一是root.left那么这是共同的祖先。一种是root.left ，另一种是低于它。

为什么返回p如果root == p，这个祖先怎么样？

当nodesFromLeft是1，则一个节点是root.left下，另一个是 要么root，root.right下，或者不存在于树存在。如果它是root, 那么这就是祖先。一个不是root，另一个是在左边。

在最后两行检查它在root.right下或不在树中的情况。