korser
BAN USERBFS version without recursion
1. Go through the tree level by level
2. Find level of the first leaf
3. For each next leafs check level, if levels are different, return false
4. At the end of BFS return true,
public static bool OnSameLevel(Tree tree)
{
if (tree == null)
{
return true;
}
var from = new Queue<Tree>();
var to = new Queue<Tree>();
from.Enqueue(tree);
var levelOfFirstLeaf = -1;
var currentLevel = 1;
while (from.Count > 0 || to.Count > 0)
{
var node = from.Dequeue();
if (node.Left != null)
{
to.Enqueue(node.Left);
}
if (node.Right != null)
{
to.Enqueue(node.Right);
}
// leaf node process
if (node.Left == null && node.Right == null)
{
if (levelOfFirstLeaf == -1)
{
// we found first level with leaf node
levelOfFirstLeaf = currentLevel;
}
else
{
// we found leaf node again, if this one the other level, then return false
if (levelOfFirstLeaf != currentLevel)
{
return false;
}
}
}
if (from.Count != 0)
{
continue;
}
// switching to the next level
currentLevel++;
var tmp = from;
from = to;
to = tmp;
}
// all leafs on the same level
return true;
}
public static MyNode reverselist(MyNode list, int k)
{
if (list == null) return list;
if (k <= 0) return list;
MyNode head = list;
int k1 = k;
k--;
while (list.next != null && k > 0)
{
MyNode tmp1 = head;
head = list.next;
MyNode tmp = head.next;
head.next = tmp1;
list.next = tmp;
k--;
}
if (k > 0) return null;
list.next = reverselist(list.next, k1);
return head;
}
- korser February 13, 2014