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

我有以下代码来找到最低的共同祖先（同时具有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, a, b); else return root; } 

二叉搜索树是

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

题

以下情况失败：

LCA（4,8）= 20但应该是8。

LCA（8,12）= 20但应该是8

LCA（8,23）= 20，不存在数字（23）作为参数。

有什么想法吗？

Node是哪里的

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

Answer 1

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

 public static Node LCA(Node root, Node a, 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,small) && 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); } 

Answer 2

IData是否定义了相等运算符（==）？ 如果没有，您只是比较参考而不是对象本身。

这很好地解释了它： http ： //www.ikriv.com/en/prog/info/dotnet/ObjectEquality.html

Answer 3

这是C＃版本：

 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace LCA { class Node { public Node(int data, Node a, Node b) { IData = data; LeftChild = a; RightChild = b; } public int IData { get; set; } public Node RightChild { get; set; } public Node LeftChild { get; set; } } class Program { static Node a = new Node(10, null, null); static Node b = new Node(14, null, null); static Node ab = new Node(12, a, b); static Node c = new Node(4, null, null); static Node ac = new Node(8, c, ab); static Node d = new Node(22, null, null); static Node root = new Node(20, ac, d); static void Main(string[] args) { string line; line = Console.ReadLine(); string[] ip = line.Split(' '); int ip1 = -1; int ip2 = -1; if (ip.Length == 2) { Int32.TryParse(ip[0], out ip1); Int32.TryParse(ip[1], out ip2); int i = -1; Node node = null; Node node1 = new Node(ip1, null, null); Node node2 = new Node(ip2, null, null); if (contains(root, node1)) { if (!contains(root, node2)) node = node1; } else { if (!contains(root, node2)) node = new Node(-1, null, null); else node = node2; } if (node == null) node = LCA(root, node1, node2); Int32.TryParse(node.IData.ToString(), out i); Console.WriteLine(i); Console.ReadLine(); } } public static Node LCA(Node root, Node a, Node b) { if (root == null) return 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) { do { current = current.RightChild; } while (current != null && current.IData < small.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 // Not both in the same subtree { if (contains(current, small) && 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); } } } 

Answer 4

干得好：

 Console.WriteLine("\n\n /* Lowest Common Ancestor */"); int v1 = 4, v2 = 8; Node lca = LCA(Root, v1, v2); Console.WriteLine("LCA of {0} and {1} is: {2}", v1, v2, (lca != null ? lca.Data.ToString() : "No LCA Found")); public static Node LCA(Node root, int v1, int v2) { if (root == null) return null; if (root.Data > v1 && root.Data > v2) return LCA(root.Left, v1, v2); else if (root.Data < v1 && root.Data < v2) return LCA(root.Right, v1, v2); else return root; } 

Answer 5

只需添加c＃迭代版本，以便在二进制搜索树中查找共同的祖先以供参考：

 public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2) { //ensure both elements are there in the bst var n1 = this.BstFind(e1, throwIfNotFound: true); if(e1 == e2) { return n1; } this.BstFind(e2, throwIfNotFound: true); BinaryTreeNode leastCommonAcncestor = this._root; var iterativeNode = this._root; while(iterativeNode != null) { if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2)) { iterativeNode = iterativeNode.Left; } else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2)) { iterativeNode = iterativeNode.Right; } else { //ie; either iterative node is equal to e1 or e2 or in between e1 and e2 return iterativeNode; } } 

Find的定义如下

 public BinaryTreeNode Find(int e, bool throwIfNotFound) { var iterativenode = this._root; while(iterativenode != null) { if(iterativenode.Element == e) { return iterativenode; } if(e < iterativenode.Element) { iterativenode = iterativenode.Left; } if(e > iterativenode.Element) { iterativenode = iterativenode.Right; } } if(throwIfNotFound) { throw new Exception(string.Format("Given element {0} is not found", e); } return null; } 

BinaryTreeNode定义为：

 class BinaryTreeNode { public int Element; public BinaryTreeNode Left; public BinaryTreeNode Right; } 

** **测试

 [TestMethod] public void LeastCommonAncestorTests() { int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 }; int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22}; BinarySearchTree bst = new BinarySearchTree(); foreach (int e in a) { bst.Add(e); bst.Delete(e); bst.Add(e); } for(int i = 0; i < b.Length; i++) { var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]); Assert.IsTrue(n.Element == b[i]); } } 

Answer 6

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