二叉树中两个节点的第一个共同祖先-Java 学习之路

我试图从破解代码访谈的书中解决问题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;
}

1 回答

2
如果是关于发现缺陷：

Flaw #1: 我认为你的代码中存在太多的拼写错误，这可能会使访问者在第一次阅读代码时感到困惑（而且你不会使访谈者感到困惑并且使这些东西变得混乱 . ）他偏离重要的事情，这是理解你解决问题的方式 .

抛开错别字，我认为另一个缺陷是这段代码难以理解 . 我认为其中一个原因是因为你在函数体内（在开头，中间和结尾）都有'return'语句 . 这应该避免使用，以支持可读性 .

通常我的方法是以下列方式组织代码：
- 基本边界案例检查（可能包括退货）
- 函数的主体（在任何条件下都不应该返回）
- 最后检查和最终返回
但是当你在中间有返回语句时，它会让读者更难想象流程 .

Flaw #3 ：我认为你' and ' a ' and ' 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;
}
```
在上面的代码中，我将在一个名为searchNodes的不同函数中实际搜索'a'和'b'的任务分开，如果你的面试官要求它，这很容易实现 . 但他甚至可能不这样做 . 如果他这样做，那时他已经理解了你的方法，所以现在更容易“使代码更复杂”，而不会让访问者感到困惑 .

我希望这有帮助 .
回复于 2024-05-03T03:26:51+08:00

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

1 回答

相关问题