c# - 在最深的二叉树中查找元素的最佳解决方案是什么

Question

最近我有一个关于在二叉树中查找元素的面试问题。我用 C# 编写了递归和迭代解决方案，但问题是在测试用例中，当我们有一个包含 1000000 个节点的树并且所有节点都在左侧时。面试官对我说，我的解决方案(递归和迭代)没有为这种情况节省足够的内存 RAM，我不明白如何改进我的解决方案。

    // 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;
     }

Answer 1

您的迭代解决方案中有一些错误。

// 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;
 }