c# - 如何找出 BST 中最深的节点？

Question

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

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

Answer 1

(假设你想要得到的是树的高度，包括作为参数给出的节点)

对于空树(node == null)，您将获得 -1 的深度。 对于具有 1 个节点的树，您将收到:

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

等等，返回 0 应该可以解决问题，但总体思路没问题。

至于优化...如果您对这棵树的了解只是它是二叉树，那么这是您在不缓存节点高度的情况下可以获得的最佳结果。

至于找到最近的叶子，您可以使用 BFS算法可以有效地做到这一点，因为它会水平地发现节点，然后当你发现第一个叶子时你可以停止。

BFS 伪代码:

nodes.enqueue( tuple(node, 1)) //enqueue node with height == 1
while(nodes.count > 0)
{
  (node, h) = nodes.dequeue()
  if (node.left == null && node.right == null) return h; //If it's first leaf we've found, return it's height.

  //Enqueue our childs with their height
  if (node.left != null)
    nodes.enqueue(node.left, h+1);
  if (node.right != null)
    nodes.enqueue(node.right, h+1);
}