Как лучше всего найти элемент в самом глубоком бинарном дереве? - PullRequest
Новая
       14

Как лучше всего найти элемент в самом глубоком бинарном дереве?

0 голосов
/ 26 ноября 2018

Недавно у меня был вопрос на собеседовании, и он касался поиска элемента в двоичном дереве, я кодирую рекурсивное и итеративное решение с помощью c #, но проблема заключалась в том, что в тестовых случаях, когда у нас есть дерево с узлом 1000000 и все онинаходятся на левой стороне.Интервьюер сказал мне, что мои решения (recusive и iteratif) не экономят оперативную память, достаточную для этого случая, и я не понимаю, как улучшить свое решение 

    // recusive Mode
    public Node Find(int v)
    {
        if(v == value)
        {
            return this;
        }else if(v <value){
            if (left == null) return null;
            return left.Find(v);

        }else{
            if (right == null) return null;
            return right.Find(v);
      }
    }

    // iterative
    public Node Find(int v)
    {
      Node current = this;
      while(value != v && current != null)
      {
        if (v < current.value)
        {
           if (current.left == null){ current = null};
           else{current = current.left};
        }
        else
        {
          if (current.right == null) { current = null};
           else{current = current.right };
        }
      }
      return current;
     }

Мне нужны советы для решения этой проблемывопрос?

1 Ответ

0 голосов
/ 26 ноября 2018

В вашем итеративном решении есть некоторые ошибки. 

// iterative
public Node Find(int v)
{
  Node current = this;
  // Here you need to compare current.value instead of just value
  // Also, to use short-circuiting you need to put null-check first
  // otherwise you might access current.value while current is null
  while(current != null && current.value != v)
  {
    if (v < current.value)
    {
       //if (current.left == null){ current = null};
       //else{current = current.left};
       current = current.left; // the same as two commented out lines
    }
    else
    {
      //if (current.right == null) { current = null};
      //else{current = current.right };
      current = current.right; // the same as two commented out lines
    }
  }
  return current;
 }
...