在二叉搜索树找到最低的共同祖先

本文介绍了在二叉搜索树找到最低的共同祖先的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有下面的代码来找到最低的共同祖先（同时具有A和B的后裔最低节点）：

 公共静态节点LCA（根节点，节点A，节点b）
 {
如果（根== NULL）
返回NULL; 
 
如果（root.IData == || a.IData == root.IData b.IData）
返回根; 
 
如果（root.RightChild = NULL&放大器;！及（root.RightChild.IData == || a.IData == root.RightChild.IData b.IData））
返回根; 
 
如果（root.LeftChild = NULL&放大器;！及（root.LeftChild.IData == || a.IData == root.LeftChild.IData b.IData））
返回根; 
 
如果（root.IData> a.IData和放大器;&安培; root.IData> b.IData）
返回LCA（root.LeftChild，A，B）; 
否则如果（root.IData< a.IData&放大器;&安培; root.IData< b.IData）
返回LCA（root.RightChild，A，B）; 
，否则
返回根; 
}

的

二叉搜索树是

  20 
 / \ 
 8月22日
 / \ 
 4月12日
 / \ 
 10 14

问

有没有以下情况：

Any thoughts?

Where Node is

class Node
{
 public int IData {get; set;}
 public Node RightChild {get; set;}
 public Node LeftChild {get; set;}
}

解决方案

public static Node LCA(Node root, Node a, Node b)
{

    if (root == null)
        return null;

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

    return root;
}

这篇关于在二叉搜索树找到最低的共同祖先的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！