1

我试图从破解代码面试的书中解决问题 4.7（非常酷的书！）。

设计一个算法并编写代码来找到二叉树中两个节点的第一个共同祖先。避免在数据结构中存储额外的节点。注意：这不一定是二叉搜索树。

我想出了这个解决方案，它甚至与书中提供的解决方案都不相近。我想知道是否有人可以找到它的任何缺陷？

解决方案：我创建了一个包装类来保存第一个共同祖先（如果找到的话）和 2 个布尔值来跟踪递归搜索树时是否找到了 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;
}
4

1 回答 1

2

如果是关于发现缺陷：

缺陷#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 的函数中，如果面试官要求，这很容易实现。但他甚至可能不会那样做。如果他这样做了，那时他已经理解了你的方法，所以现在更容易“让代码更复杂一点”而不会让面试官感到困惑。

我希望这有帮助。

于 2014-10-20T17:32:45.383 回答