如何查找二叉搜索树中最深的节点？

Question

private int Depth(TreeNode node)
{
    if (node == null)
    {
        return -1;
    }
    else
    {
        return 1 + Math.Max(Depth(node.LeftNode),Depth(node.RightNode));
    }
}

我写了一个方法来找到最深的节点，但是我不确定这个方法是否正确。
这是找到最深节点的正确方式吗？

- Desire

Answer 1

（假设你想得到的是包括作为参数给定的节点的树的高度）

对于空树（node == null），您将得到深度为-1。

对于只有1个节点的树，您将收到：

1 + max(-1, -1) = 0

关于问题的解决，返回0应该能解决问题，但这个思路是可行的。

至于优化......如果您只知道这棵树是二叉树，那么在不缓存节点高度的情况下，这是您能得到的最好结果。

至于寻找最近的叶子节点，您可以使用BFS算法来高效完成，因为它将以水平方式遍历和发现节点，然后在发现第一个叶子节点时停止。

BFS伪代码：

nodes.enqueue( tuple(node, 1)) //将高度为1的节点排队
while(nodes.count > 0)
{
  (node, h) = nodes.dequeue()
  if (node.left == null && node.right == null) return h; //如果我们发现的是第一个叶子节点，则返回其高度。
//将所有孩子节点和它们的高度入队
  if (node.left != null)
    nodes.enqueue(node.left, h+1);
  if (node.right != null)
    nodes.enqueue(node.right, h+1);
}

- Marcin Deptuła

---

那么最小深度节点呢？我认为离根节点更近/最近的节点是最小深度节点。 - Desire

嗯，你在问最深的节点，你是如何理解“最深”的呢？在我的理解中，它是指具有尽可能多的父节点直到根节点的节点，这使它成为深度最高的节点。 - Marcin Deptuła

Answer 2

二叉搜索树的最深节点被称为高度。

在这里，您可以了解如何计算二叉搜索树的高度。

基本上你是对的。

- dimme

---

那么最小深度节点呢？我认为靠近根节点的节点是最小深度节点。 - Desire

你想要的可能是距离根节点最近的第一个叶子节点。你可以通过在到达第一个空节点时停止递归并立即返回该值来实现这一点。 - dimme

请您通过迭代方法更清晰地解释一下。 - Desire