- #1

SlurrerOfSpeech

- 141

- 11

Code:

```
using System;
using System.Collections.Generic;
using System.Linq;
class Node
{
public int Val { get; set; }
public Node Right { get; set; }
public Node Left { get; set; }
public Node(int val) { Val = val; }
}public class Solution
{
static Node _root = null;
static void AddToTree(int val)
{
if(_root == null)
_root = new Node(val);
for(Node cur = _root; ; )
{
if(cur.Val < val)
{
if(cur.Right == null)
{
cur.Right = new Node(val);
break;
}
else
{
cur = cur.Right;
}
}
else if(val < cur.Val)
{
if(cur.Left == null)
{
cur.Left = new Node(val);
break;
}
else
{
cur = cur.Left;
}
}
else
{
break;
}
}
}
static Node NearestCommonAncestor(int i, int j)
{
int smaller = i < j ? i : j,
larger = i + j - smaller;
return NearestCommonAncestor(smaller, larger, _root);
}
static Node NearestCommonAncestor(int i, int j, Node root)
{
if(root == null)
return null;
else if(root.Val < i)
return NearestCommonAncestor(i, j, root.Right);
else if(root.Val > j)
return NearestCommonAncestor(i, j, root.Left);
else
return root;
}
static int DistanceToNode(Node start, int val)
{
int d = 0;
for(Node cur = start; ; )
{
if(cur == null)
return -1;
else if(cur.Val < val)
{
cur = cur.Right;
d += 1;
}
else if(cur.Val > val)
{
cur = cur.Left;
d += 1;
}
else
break;
}
return d;
}
static int DistanceBetweenNodes(int i, int j)
{
Node nca = NearestCommonAncestor(i, j);
if(nca == null)
return -1;
int di = DistanceToNode(nca, i);
int dj = DistanceToNode(nca, j);
if(di == -1 || dj == -1)
return -1;
return di + dj;
}
public static void Main(String[] args)
{
int[] vals = { 2, 1, 5, 3, 8 };
foreach(int i in vals)
AddToTree(i);
/*
Now the tree should look like
2
/ \
1 5
/ \
3 8
*/
IEnumerable<string> results =
from x in vals
from y in vals
select string.Format
(
"Distance between {0} and {1} is {2}",
x, y, DistanceBetweenNodes(x,y)
);
foreach(string message in results)
Console.WriteLine(message);
}
}
```