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

Question

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

我的问题：
如何在多种方式中选择最佳方式？与我直接的幼稚方法相比，这种最佳方法的 advantages/disadvantages 是什么？

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

问题陈述

你得到了指向二叉搜索树根的指针和两个值 v1 和 v2。您需要 return 二叉搜索树中 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;
 }

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

Answer 1

好吧，这就是我解决问题的方法。这取决于您正在处理二叉搜索树这一事实。

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

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

就优点而言，您实际上只是在浪费隐式递归调用堆栈 space，它最后还必须展开。我们在 O(log N) 中的两个实现运行，因为您将在最坏的情况下检查 log N - 1 节点，其中 v1 和 v2 是底部的直接兄弟节点一棵完整的树。

实施

如果 v1 < v2 交换 v1 和 v2（删除 min 和 max 检查的需要）。这隐含地包含 both 你的 if 检查 v1 < root < v2 和 v2 < root < v1.
当当前节点的值小于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;
}

Answer 2

更好的方法通常有：

更好的时间or/andspace复杂度。
可读代码。
更好地管理边缘情况。
我相信大多数时候它会产生更小的代码。

如果我们查看您的代码：

 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;
 }

时间或 Space 复杂性方面你的代码也很有效，我想谈几点可读性。

你所有的if陈述return什么的，其实不用写else if，if就够了。

当 root 是 null 或 v1 或 v2 时，你只是 returning root，所以你可以结合前两个条件。

注意： 如果您担心您的元素不在树中，您可以在调用此函数之前始终检查它们是否存在。我喜欢这种方式，您可能想添加其他额外条件，如果需要，还可以添加 return null。

 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.
}

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

What is the best approach? Binary Search Tree : Lowest Common Ancestor using only if statements

java

tree

binary-tree

binary-search-tree

data-structures