当一个或两个节点不存在时，查找最低公共祖先BST [英] Find Lowest Common Ancestor BST when one or both node(s) doesnt exist

问题描述

我们可以轻松地使用代码在二进制搜索树中找到LCA:-

We can easily use the code to find LCA in Binary Search Tree:-

public static Node FindLCA(Node root, Node a, Node b)
{           
    if (root == null)
        return null; 

    if (root.IData == a.IData || root.IData == b.IData)
        return root;

    if (root.RightChild != null && (root.RightChild.IData == a || root.RightChild.IData == b))
        return root;

    if (root.LeftChild != null && (root.LeftChild.IData == a || root.LeftChild.IData == b))
        return root;

    if (root.IData > a.IData && root.IData > b.IData)
        return FindLCA(root.LeftChild, a, b);
    if (root.IData < a.IData && root.IData < b.IData)
        return FindLCA(root.RightChild, a, b);
    else
        return root;
}

想知道如果节点之一不存在时该如何处理?一个简单的可能选择是，找到BST中是否存在节点-可以在O(LogN)时间完成，然后如有必要，调用FindLCA?还有其他任何选择，而无需先找到密钥是否存在?

Was wondering how to handle in case one of the nodes doesn't exist? One easy possible option could be, find if the nodes exist in the BST - this can be done in O(LogN) time and then if necessary call FindLCA? Any other options without first finding if keys exist or not?

编辑 我意识到我早先还缺少一些条件，因此添加了这些条件，并且还基于以下vvijay的回答.

EDIT I realized that I was missing some more conditions earlier, added them and also based on vvijay's answer below.

                             20
                     8                 22
               4           12 
                       10       14

问题:

1. 但是现在它找不到8，22的LCA并说22而不是20.
2. LCA(8，12)是8还是20-我认为应该基于Wiki的LCA(即，我们允许节点成为其自身的后代)的定义为8.

有什么想法建议吗?

推荐答案

我认为您可以将不良情况分开.

I think you can separate out the bad cases.

if (root == null) return null;
if (root.Idata == a.Idata || root.Idata == b.Idata) return root;

或仅更改return null以在代码中返回root.因此，返回值为null意味着您在树中没有至少一个查询节点.

or just change the return null to return root in your code. So null return value would mean you don't have atleast one of the query nodes in the tree.

这篇关于当一个或两个节点不存在时，查找最低公共祖先BST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！