什么是最佳方法？二叉搜索树：仅使用if语句查找最近公共祖先

Question

我用只有if语句的方法解决了问题。其他方法也可以解决。我刚开始学编程，所以我想不到使用其他数据结构来解决这个问题。

我的问题是：怎样在众多方法中选择最佳方法？与我直接朴素的方法相比，这种最佳方法有什么优劣势？

不仅针对这个问题，一般来说，如何找出任何问题的可能解决方案？

问题陈述：

给定二叉搜索树的根指针和两个值v1和v2。你需要返回二叉搜索树中v1和v2的最低公共祖先(LCA)。你只需要完成函数。

我的代码：

static Node lca(Node root,int v1,int v2)
 { 
    Node r = root;
    if( r == null){
        return null;
    }
    else if(r.data == v1 || r.data == v2){
        return r;
    }
    else if(r.data > v1 && r.data < v2){
        return r;
    }
    else if(r.data > v2 && r.data < v1){
        return r;
    }
    else if( r.data > v1 && r.data > v2){
        lca(r.left, v1, v2);
    }
    else if( r.data < v1 && r.data < v2){
        lca(r.right, v1, v2);
    }
   return null;
 }

问题链接: https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor

这道题目要求我们找到二叉搜索树中两个节点的最近公共祖先。为了解决这个问题，我们可以通过递归遍历二叉搜索树来寻找最近公共祖先。具体实现时，我们可以分别判断当前节点是否大于或小于两个给定节点，以此决定向左子树或右子树递归查找。如果当前节点既不大于也不小于两个节点，则说明当前节点就是它们的最近公共祖先。

- Charan

---

除了lca(r.left...)和lca(r.right...)缺少两个return之外，解决方案似乎是正确的。正如您所正确识别的那样，LCA将是大于v1但小于v2（或反之亦然）的数字。 - biziclop

Answer 1

好的，这是我解决问题的方法。这依赖于您正在处理二叉搜索树。

对于任何给定的节点，只有当min(v1,v2)在其左子树中，并且max(v1,v2)在其右子树中时，它才可以成为LCA。如果不是这样，则当前节点显然不能是祖先，因为v1或v2可能不是后代。继续遍历树，直到满足LCA条件为止。

您的解决方案是正确的，并且您已经掌握了直觉，但我们可以剥离递归并简单地执行迭代BST查找，这也隐含了您的if检查。

在优点方面，您实际上只是浪费了隐式递归调用堆栈空间，它还必须在最后解开。由于在最坏情况下，即v1和v2是完整的树底部的直接兄弟姐妹，您的两个实现都运行在O(log N)中，因为您将检查log N-1个节点。

实现

1. 如果v1<v2，请交换v1和v2（删除min和max检查的需要）。这隐含地包含了您的if检查v1<root<v2和v2<root<v1。

2. 当当前节点的值小于v1（v1在右子树中）或大于v2时，向v1或v2移动向。这将替换您的递归遍历。

这是我检查过的快速实现：

static Node lca(Node root, int v1, int v2)    {
    if (root == null) return null;
    if (v1 > v2) {          
        int temp = v2;
        v2 = v1;
        v1 = temp;
    }
    while (root.data < v1 || root.data > v2) {
        if (root.data < v1)      root = root.right;
        else if (root.data > v2) root = root.left;
    }       
    return root;
}

- Aaron Zou

---

非常感谢您提供详细的解释和更好的代码。 - Charan

如果您满意的话，可以接受答案（勾选）。如果有任何需要澄清的地方，请告诉我，谢谢！ - Aaron Zou

我想接受两个答案，但我不认为这是可能的。这就是为什么我给两个答案点赞的原因。 - Charan

我在HackerRank上提交了一段类似的代码，使用了Do While循环，在一个测试用例中失败了。 - user1229441

Answer 2

更好的方法通常具有以下特点：

1. 更好的时间和/或空间复杂度。

2. 易于阅读的代码。

3. 更好地处理边缘情况。

4. 我相信大多数情况下它会产生更小的代码。

如果我们看一下你的代码：

 static Node lca(Node root,int v1,int v2)
 { 
     Node r = root;
    if( r == null){
       return null;
    }
    else if(r.data == v1 || r.data == v2){
       return r;
    }
    else if(r.data > v1 && r.data < v2){
       return r;
    }
    else if(r.data > v2 && r.data < v1){
      return r;
    }
    else if( r.data > v1 && r.data > v2){
       lca(r.left, v1, v2);
    }
    else if( r.data < v1 && r.data < v2){
      lca(r.right, v1, v2);
    }
    return null;
 }

您的代码在时间和空间复杂度方面也很高效，我想谈谈可读性问题。

1. All your if statements return something, so actually don't need to write else if, just if will be enough.

2. when root is null or v1 or v2, you are returning root only, so you can combine first two conditions.

   NOTE: If you are worried about your elements not present in the tree, you can always check for their existence before call this function. I like it this way, you might want to add your other extra conditions and return null if you want to.

    static Node lca(Node root,int v1,int v2)
    { 
       Node r = root;
      if( r == null || r == v1 || r == v2){
          return root;
      }
   
     if( r.data > v1 && r.data > v2){
         lca(r.left, v1, v2);
     }
   
     if( r.data < v1 && r.data < v2){
         lca(r.right, v1, v2);
     }
     return root; // instead of checking the other two conditions, you can directly return the root.
   }
   

- Karthik

---

我仍然认为，在这种情况下，递归实现是不必要的，因为遍历是如此直接（二分查找）。我同意您在简化返回值计算方面的观点。 - Aaron Zou

@AaronZou 你说得没错，但这很大程度上取决于个人选择和代码风格。由于OP刚开始编码，我认为递归是解决问题的一种简单且更直观的方式。 - Karthik

@karthik 非常感谢你指出我的错误，并解释了更好的方法。 - Charan