c# – 在二叉搜索树中查找最低共同祖先

概述我有以下代码来查找最低共同祖先(同时具有a和b作为后代的最低节点)： public static Node LCA(Node root, Node a, Node b){ if (root == null) return null; if (root.IData == a.IData || root.IData == b.IData) retur 我有以下代码来查找最低共同祖先(同时具有a和b作为后代的最低节点)：

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 root;    if (root.RightChild != null && (root.RightChild.IData == a.IData || root.RightChild.IData == b.IData))        return root;    if (root.leftChild != null && (root.leftChild.IData == a.IData || root.leftChild.IData == b.IData))        return root;    if (root.IData > a.IData && root.IData > b.IData)        return LCA(root.leftChild,a,b);    else if (root.IData < a.IData && root.IData < b.IData)        return LCA(root.RightChild,b);    else        return root;}

二叉搜索树是

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

题

以下情况失败：

LCA (4,8) = 20 but should be 8.

LCA (8,12) = 20 but should be 8

LCA (8,23) = 20,non-existent number (23) as parameter.

有什么想法吗？

Node在哪里

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

解决方法 如果root的IData与a和b都不同,但是root的子节点之一具有与两者中的任何一个相同的IData,则返回root,但是根据您的定义,如果两个节点都在同一个节点中,则应返回子节点子树.由于您还要检查两个节点是否实际位于树中,因此必须在返回之前执行该检查.

public static Node LCA(Node root,Node b){    if (root == null) return null;    // what if a == null or b == null ?    Node small,large,current = root;    if (a.IData < b.IData)    {        small = a;        large = b;    }    else    {        small = b;        large = a;    }    if (large.IData < current.IData)    {        do        {            current = current.leftChild;        }while(current != null && large.IData < current.IData);        if (current == null) return null;        if (current.IData < small.IData) return LCA(current,small,large);        // if we get here,current has the same IData as one of the two,the two are        // in different subtrees,or not both are in the tree        if (contains(current,small) && contains(current,large)) return current;        // at least one isn't in the tree,return null        return null;    }    else if (current.IData < small.IData)    {        // the symmetric case,too lazy to type it out    }    else // Not both in the same subtree    {        if (contains(current,large)) return current;    }    return null; // at least one not in tree}public static bool contains(Node root,Node target){    if (root == null) return false;    if (root.IData == target.IData) return true;    if (root.IData < target.IData) return contains(root.RightChild,target);    return contains(root.leftChild,target);}

@H_301_56@ 总结

以上是内存溢出为你收集整理的c# – 在二叉搜索树中查找最低共同祖先全部内容，希望文章能够帮你解决c# – 在二叉搜索树中查找最低共同祖先所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。