SkyClouds
BAN USER- 0of 0 votes
AnswersHow to check if a binary tree is a binary search tree?
- SkyClouds in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm
Djikstra's Algorithm Implementation in C#
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Test.CareerCup
{
public class C17297667
{
private int size;
public int[] weight;
private int[] previous;
private int[] distance;
private List<int> set = new List<int>();
public C17297667(int size)
{
this.size = size;
}
public void Init()
{
weight = new int[size * size];
previous = new int[size * size];
distance = new int[size * size];
var random = new Random();
// init weight
for (int i = 0; i < size * size; i++)
{
weight[i] = random.Next(1, 20);
previous[i] = -1;
distance[i] = int.MaxValue;
set.Add(i);
}
}
public void ShowMatrix()
{
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
Console.Write("{0,4}, ", weight[i * size + j]);
}
Console.WriteLine();
}
}
private void CheckDistance(int current, int target)
{
int tmp_dist = distance[current] + weight[target];
if (tmp_dist < distance[target])
{
distance[target] = tmp_dist;
previous[target] = current;
}
}
public IEnumerable<int> GetShortestPath(int start, int end, out int minValue)
{
List<int> path = new List<int>();
distance[start] = 0;
while (set.Count > 0)
{
// find point with min distance in set
int node = (from p in set orderby distance[p] select p).First();
// remove it from set
set.Remove(node);
// if node == end, reach the target
if (node == end) break;
// check neighbors
// up
if (node - size > 0)
{
CheckDistance(node, node - size);
}
// down
if (node + size < size * size)
{
CheckDistance(node, node + size);
}
// left
if (node % size != 0)
{
CheckDistance(node, node - 1);
}
// right
if (node % size != size - 1)
{
CheckDistance(node, node + 1);
}
}
minValue = distance[end];
if (distance[end] == int.MaxValue)
{
return null; // no result
}
else
{
int current = end;
do
{
path.Insert(0, current);
current = previous[current];
} while (current != start);
path.Insert(0, current);
return path;
}
}
}
}
Calling:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Test.CareerCup;
namespace Test
{
class Program
{
static void Main(string[] args)
{
FindShortestPath();
}
static void FindShortestPath()
{
C17297667 c = new C17297667(8);
c.Init();
c.ShowMatrix();
int minValue;
var path = c.GetShortestPath(0, 63, out minValue);
Console.WriteLine("Min path value = " + minValue);
Console.WriteLine("Min path is:");
foreach (var p in path)
{
Console.WriteLine("{0}, {1}, wight = {2}", p / 8, p % 8, c.weight[p]);
}
}
}
}
Implemented by C#.
public class BinaryTree {
public BinaryTree Left;
public BinaryTree Right;
public int Value;
}
public BinaryTree FindCeilingRecursively(BinaryTree node, int n) {
if(node == null) return null;
if(n >= node.Value) {
return FindCeiling(node.Right, n);
} else {
BinaryTree result = FindCeiling(node.Left, n);
return result == null ? node : result;
}
}
public BinaryTree FindCeilingReitoratively(BinaryTree node, int n) {
if(node == null) return null;
BinaryTree result = null, p = node;
while (p != null) {
if(n >= node.Value) {
p = p.Right;
} else {
result = p;
p = p.Left;
}
}
return result;
}
public static find_max_subarray(int[] a) {
// check arguments
if(a == null || a.Length == 0) throw new ArgumentNullException();
int max = a[0], tmp_max = a[0];
foreach(var i in a) {
if(tmp_max < 0) {
tmp_max = i;
} else {
tmp_max += i;
}
max = tmp_max > max ? tmp_max : max;
}
}
The simplest way is to save the predecessor in a variable, and then update it while traversing the BT with post-order.
1) set predecessor = null
2) traverse BT with post-order
3) if current_node == input_node {
return predecessor;
} else {
predecessor = current_node
}
4) goto step 3)
I traverse the binary tree recursively:
public class BinaryTree {
public BinaryTree Left;
public BinaryTree Right;
public int Value;
}
/*
* action value meaning:
* 0, to print leftmost + leaves + rightmost
* 1, to print leftmost + leaves
* 2, to print rightmost + leaves
* 3, to print leaves
*/
public static Print(BinaryTree node, int action) {
if(node == null) {
throw new ArgumentNullException("node");
}
if(action != 3) {
// print current value
Console.Write("{0} ", node.Value);
}
int left_action = -1, right_action = -1;
switch(action) {
case 0: left_action = 1, right_action = 2; break;
case 1: left_action = 1, right_action = 3; break;
case 2: left_action = 3, right_action = 1; break;
case 3: left_action = 3, right_action = 3; break;
default:
throw new ArgumentException("action: out of range!");
}
if(node.Left != null) Print(node.Left, left_action);
if(node.Left == null && node.right == null && action == 3) {
// print current value
Console.Write("{0} ", node.Value);
}
if(node.right != null) Print(node.Right, right_action);
}
Here is my code:
public static string Get(int n)
{
if (n < 0) throw new ArgumentException();
if (n == 0) return "A";
var s = new StringBuilder();
int i = n;
while (i != 0)
{
s.Insert(0, (char)('A' + i % 26));
i = i / 26;
}
if (s.Length > 1) s[0]--;
return s.ToString();
}
1. sort direction is not an issue, cause if descending, just traverse the array from tail.
2. only check <= is fine, it will cover the duplicate case.
here is the c# code
public static bool IsSet(int[] array) {
if(array == null || array.Length == 0) return false;
if(array[0] <= 0) return false; // if ascending, only need to check once
for(int i=0; i<array.Length-1; i++) {
if(array[i] >= array[i+1]) return false;
}
return true;
}
My algo is:
- SkyClouds May 15, 20131st, traverse the string and get the total length of the result string, assuming len = N.
2nd, traverse the string from tail, and then parse and write the new string also from the tail, a[N-1].
In this solution, time complexity is O(n).