java - 二叉树中两个节点的第一个共同祖先

Question

我试图解决《破解代码面试》这本书中的问题 4.7(非常酷的书!)。

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.

我想出了这个解决方案，它与书中提供的解决方案相差甚远。不知道有人能找出其中的缺陷吗？

解决方案:我创建了一个包装类来保存第一个共同祖先(如果找到)和 2 个 boolean 值来跟踪在递归搜索树时是否找到 a 或 b。请阅读下面代码中添加的注释。

public static void main (String args[]){
    NodeTree a, b, head, result; //initialise and fill with data
    fillTreeTestData(head);
    pickRandomNode(a);
    pickRandomNode(b);
    result = commonAnsestor(a,b,head);
    if(result != null)
        System.out.println("First common ansestor "+result);
    else
        System.out.println("Not found");

}

class TreeNode{
    Object value;
    TreeNode right, left;
}

class WraperNodeTree{
    boolean found_a;
    boolean found_b;
    NodeTree n;

    WraperNodeTree (boolean a, boolean b, NodeTree n){
        this.n = n;
        this.a = a;
        this.b = b;
    }
}

static WraperNodeTree commonAnsestor(NodeTree a, NodeTree b, NodeTree current){
    // Let's prepare a wraper object
    WraperNodeTree wraper = new WraperNodeTree(false, false, null);
    // we reached the end
    if(current == null) return wraper;

    // let's check if current node is either a or b
    if(a != null)
        wraper.found_a = current.value.equals(a.value);
    else if(b != null)
        wraper.found_b = current.value.equals(b.value);
    else
        return wraper; // if both are null we don't need to keep searching recoursively

    // if either a or b was found let's stop searching for it for performance
    NodeTree to_search_a = wraper.found_a ? null : a;
    NodeTree to_search_b = wraper.found_b ? null : b;

    // let's search the left
    WraperNodeTree wraperLeft  = common(to_search_a,to_search_b,current.left);
    // if we already have a common ancester just pass it back recoursively
    if(wraperLeft.n != null) return wraperLeft;

    WraperNodeTree wraperRight = common(to_search_a,to_search_b,current.right);
    if(wraperRight.n != null)return wraperRight;

    // keep the wraper up to date with what we found so far
    wraper.a = wraper.found_a || wraperLeft.found_a || wraperRight.found_a;
    wraper.b = wraper.found_b || wraperLeft.found_b || wraperRight.found_b;

    // if both a and b were found, let's pass the current node as solution
    if(wraper.found_a && wraper.found_b)
        wraper.n = current;

    return wraper;
}

Answer 1

如果是为了发现缺陷:

缺陷#1:我认为你的代码中有太多拼写错误，这可能会让面试官在第一次阅读代码时感到困惑(你不希望这样!)。例如，您可以互换地编写“NodeTree”和“TreeNode”。另外，您定义“commonAncestor()”，然后调用“common()”。这些事情让面试官感到困惑，让他偏离了重要的事情，即理解你解决问题的方式。

缺陷#2:撇开拼写错误不谈，我认为另一个缺陷是这段代码很难理解。我认为原因之一是因为你的函数体中到处都有“return”语句(在开头、中间和结尾)。为了提高可读性，“通常”应该避免这种情况。

通常我的方法是按以下方式组织代码:

1. 基本边境情况检查(可能包括返回)
2. 函数的主体(在任何条件下都不应返回)
3. 最后检查和最终返回

但是当中间有 return 语句时，读者就很难想象流程了。

缺陷#3:我认为您正在尝试使用相同的函数(commonAncestor)解决两个问题。您正在尝试搜索“a”和“b”，并跟踪共同的祖先。我认为如果这是一个面试问题，为了简单起见，您可以将这两个目标分开。

例如，考虑以下代码(可能并不完美，需要一些额外的边界检查):

/**
 * [Assumption]: If we call firstCommonAncestor(a, b, root)
 * we TRUST that root contains both a and b.
 *
 * You can (and should) discuss this
 * assumption with your interviewer.
 */
public static Node firstCommonAncestor(Node a, Node b, Node root) {
  // If root matches any of the nodes (a or b),
  // then root is the first common ancestor
  // (because of our assumption)
  if(root == a || root == b) return root;

  // Search for a and b in both sides
  SearchResult leftResult = searchNodes(a, b, root.left);
  SearchResult rightResult = searchNodes(a, b, root.right);

  // If a and b are on the same side (left or right), then we
  // call firstCommonAncestor on that side and that’s it
  if(leftResult.aFound && leftResult.bFound)
    return firstCommonAncestor(a, b, root.left);
  else if(rightResult.aFound && rightResult.bFound)
    return firstCommonAncestor(a, b, root.right);
  else {
    // If a and b are in different sides,
    // then we just found the first common ancestor
    return root;
  }
}

class SearchResult {
    boolean aFound, bFound;
}

在上面的代码中，我将实际搜索“a”和“b”的任务分离到一个名为 searchNodes 的不同函数中，如果面试官要求的话，这是相当容易实现的。但他甚至可能不会这样做。如果他这样做了，那么他已经理解了你的方法，所以现在更容易“让代码变得更复杂一些”，而不会让面试官感到困惑。

我希望这会有所帮助。