-1

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

总之，我的问题是：

1）对于这行代码：

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

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

2）对于这些代码行：

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

如果root==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;
 }
4

1 回答 1

1

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

什么时候nodesFromLeft是 2，那么p和q都在 下root.left。如果是其中之一，root.left那就是共同的祖先。一个是root.left ，另一个在它下面。

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

当nodesFromLeft为 1 时，则一个节点在下root.left，而另一个在root树下root.right，或者它不存在于树中。如果是root，那就是祖宗。一个不是root，另一个在左侧下方。

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

于 2014-09-30T12:31:16.263 回答