java - 什么是最好的方法？二叉搜索树 : Lowest Common Ancestor using only if statements

Question

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

我的问题:
如何在多种方式中选择最佳方式？与我直接的幼稚方法相比，这种最佳方法的优点/缺点是什么。

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

问题陈述

你得到了指向二叉搜索树根的指针和两个值 v1 和 v2。您需要返回二叉搜索树中 v1 和 v2 的最低公共(public)祖先 (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

Answer 1

好吧，下面是我将如何解决这个问题。这取决于您正在处理二叉搜索树这一事实。

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

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

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

实现

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