最好的方法是什么？二叉搜索树：仅使用if语句的最低公共祖先

Question

我只用if语句解决了这个问题。它可以用其他各种方法来解决。我刚刚开始编程，所以我想不出使用任何其他数据结构来解决这个问题。

我的问题:
如何在各种方法中选择最好的方法？和我的直接天真方法相比，这种最佳方法的优点/缺点是什么。

不仅针对这个问题，总的来说。如何解决任何问题？

我的代码：

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-lows-common-enthestor

Answer 1

好吧，我是这样处理这个问题的。这取决于这样一个事实，即您正在处理一个二叉搜索树。

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

您的解决方案是正确的，而且您有直觉，但是我们可以去掉递归，简单地执行迭代BST查找，它也隐式地包含if检查。

就优点而言，您实际上只是在浪费隐式递归调用堆栈空间，它还必须在最后释放该空间。我们的两个实现都在O(logn)中运行，因为在最坏的情况下，您将检查logn-1节点，其中V1和V2是位于完整树底部的直接兄弟。

实施

>

交换v1和v2如果v1 （删除对 min和 max检查的需要）。这隐式地包含 if检查 v1 和 v2 。

当当前节点的值小于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;
}