Решение для двоичного дерева Макс. Высота в одном направлении

Question

У меня была проблема, которую я попытался решить. Задача потребовала найти максимальную высоту в одном направлении бинарного дерева. НАПРИМЕР. если ветка продолжается влево, то высота продолжает увеличиваться, но если ветка затем вернется, высота будет сброшена на 1.

В C# я нашел следующее: я даже не уверен, верный.

Кто-нибудь знает оптимальное решение?

class MaxHeightInOneDirection 
{ 
    public void Run() 
    { 
     Tree a = new Tree(); 
     a.x= 20; 

     Tree b = new Tree(); 
     b.x = 21; 

     Tree c = new Tree(); 
     c.x = 12; 
     c.l = b; 
     c.r = a; 

     Tree d = new Tree(); 
     d.x = 10; 
     d.l = c; 

     Tree e = new Tree(); 
     e.x = 3; 

     Tree f = new Tree(); 
     f.x = 5; 
     f.l = e; 
     f.r = d; 

     int maxHeight = GetHeight(f)[2]; 

    } 

    public int[] GetHeight(Tree root) 
    { 
     if (root == null) 
      return new int[]{-1,-1, 0}; 

     int[] leftResult = GetHeight(root.l); 
     int[] rightResult = GetHeight(root.r); 

     // Increase left on current left 
     leftResult[0]++; 
     // Set right result on current left to 0 
     leftResult[1] = 0; 
     // Set left result on current right to 0 
     rightResult[0] = 0; 
     // Increase right on current right 
     rightResult[1]++; 

     int leftMaxSoFar = leftResult[2]; 
     int rightMaxSoFar = rightResult[2]; 

     int maxValueSoFar = Math.Max(leftMaxSoFar, leftResult[0]); 
     maxValueSoFar = Math.Max(maxValueSoFar, rightResult[1]); 
     maxValueSoFar = Math.Max(maxValueSoFar, rightMaxSoFar); 

     return new int[] { leftResult[0], rightResult[1], maxValueSoFar }; 
    } 
} 

Answer 1

Чтобы найти высоту дерева, вы можете просто использовать этот Algo: - here

в C# сделать что-то

int MaxDepth(Tree node) 
{ 
    if (node==NULL) 
     return 0; 
    else 
    {  
     int lDepth = maxDepth(node->left); 
     int rDepth = maxDepth(node->right); 

     /* use the larger one */ 
     if (lDepth > rDepth) 
      return(lDepth+1); 
     else return(rDepth+1); 
    } 
}