在二叉搜索树中找到最低的共同祖先
本文关键字：祖先 搜索树 | 更新日期: 2023-09-27 18:17:10
我有以下代码来查找最低的共同祖先(同时具有 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( 作为参数。
有什么想法吗？
节点所在的位置
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 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);
}
IData 是否定义了相等运算符 (==(？ 如果不是，则只是比较引用，而不是对象本身。
这很好地解释了它：http://www.ikriv.com/en/prog/info/dotnet/ObjectEquality.html
下面是 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);
}
}
}
你来了：
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;
}
只需添加 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
{
//i.e; either iterative node is equal to e1 or e2 or in between e1 and e2
return iterativeNode;
}
}
其中"查找"的定义如下
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]);
}
}
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;
}