最低的共同祖先破解代碼採訪解決方案

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下或不在樹中的情況。