Skip to content

Instantly share code, notes, and snippets.

@gandarez
Created March 9, 2017 01:10
Show Gist options
  • Save gandarez/67ce18820ed895638704c4163d9cb2e1 to your computer and use it in GitHub Desktop.
Save gandarez/67ce18820ed895638704c4163d9cb2e1 to your computer and use it in GitHub Desktop.
Find the longest zigzag from a binary tree
class Tree
{
public int x;
public Tree l;
public Tree r;
};
class Task3
{
public int solution(Tree T)
{
return FindZigZag(T, 0) - 1;
}
int FindZigZag(Tree t, int max)
{
if (t == null) return 0;
int lh = Count(t, true, 0);
int rh = Count(t, false, 0);
max = Math.Max(lh, rh);
max = Math.Max(max, FindZigZag(t.l, max));
max = Math.Max(max, FindZigZag(t.r, max));
return max;
}
int Count(Tree node, bool moveLeft, int count)
{
if (node == null) return count;
count = moveLeft
? Count(node.l, !moveLeft, node.l == null ? count : count + 1)
: Count(node.r, !moveLeft, node.r == null ? count : count + 1);
return count;
}
}
@another-stranger
Copy link

well... stats for the solution above:
correctness: 0%
performance: 25%
total: 12% out of 100%

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment