共通の親ノードを最小化
ツリーのアルゴリズムは、複雑さが高いかもしれませんが、再帰が便利です.
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1
{
class Node
{
public Node left;
public Node right;
public char data;
public Node(Node left, Node right, char data)
{
this.left = left;
this.right = right;
this.data = data;
}
}
class Program
{
static void Main(string[] args)
{
Node F = new Node(null, null, 'F');
Node G = new Node(null, null, 'G');
Node E = new Node(F, G, 'E');
Node D = new Node(null, null, 'D');
Node C = new Node(D, E, 'C');
Node B = new Node(null, null, 'B');
Node A = new Node(B, C, 'A');
Node Common = LCA(A, C, G);
Console.WriteLine(Common.data);
}
private static Node LCA(Node root, Node X, Node Y)
{
if (root == null) return null;
if (root == X || root == Y) return root;
Node left = LCA(root.left, X, Y);
Node right = LCA(root.right, X, Y);
if (left == null) return right;
else if (right == null) return left;
else return root;
}
}
}