在二叉搜索树中执行搜索时发生堆栈溢出错误

Question

我在对树执行二进制搜索时遇到堆栈溢出错误。我认为它有一个有效的递归终止条件，但我不确定。

TreeNode Find(TreeNode tree, int value) {
  if((tree.val == value) || tree==null) 
    return tree; 
  else if(value < tree.val) 
    return Find(tree.left, value); 
  else 
    return Find(tree.right, value); 
}

Answer 1

错误在别处（你的函数几乎完全正确）：

你的树不平衡！

你要改正的是插入函数。一个简单的插入函数只会创建一个像树一样的链表，因为如果你按 "ascending" 顺序插入元素，它们总是只添加到 "left" 或右边。

堆栈有限 space，所以如果你有一个平衡树，它可以有 40 亿个节点，它的最大高度仍然是 32。但是如果你的树即使只有很少的节点（1000 ) 它可以进入堆栈溢出。

我还建议先检查 null（这不是你的问题，把它当作一个免费的错误修复）

if(tree==null || tree.val == value )

在二叉搜索树中执行搜索时发生堆栈溢出错误

Stack Overflow error while performing Search in Binary search tree

stack-overflow

binary-search-tree