在最深的二叉树中找到元素的最佳解决方案是什么

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