Ascii值的二进制搜索树中的最大级别数？

Question

我正在对二进制搜索树进行遍历，其中每个节点都包含一个唯一的ASCII字符（根据其十进制值排序）。

我计划通过向左遍历时在路径上添加“ 0”并在向右遍历时向路径添加“ 1”来打印每个节点的路径。我计划将此值存储在数组中，但是我不知道如何计算数组的最大大小。

如果我正确，最大路径大小应等于包含唯一节点中每个ASCII字符的树的深度。我将如何计算最大深度？

注：总共有255个ASCII值。

Answer 1

使用递归可以找到二叉搜索树的最大深度。

递归：使用递归找到最大深度涉及分而治之的思想。基本上，我们将较大的问题（找到一棵树的最大深度）分为两个较小的问题（找到左子树和右子树的最大深度）。找到max（leftSubtree.depth，rightSubtree.depth）后，将其加1以考虑树的根级别。代码看起来像这样：

#Definition
def maxDepth(BSTNode root):

#Base Case
  if (root == null):
    return 0
#Find the maximum depth of left and right subtrees using recursion
  leftDepth = maxDepth(root.left)
  rightDepth = maxDepth(root.right)
  return max(left, right) + 1