javascript - 解释递归如何在算法中工作以确定二叉树的深度？

Question

我是 JavaScript 数据结构的新手，正在尝试学习二叉搜索树。我正在关注一篇博客文章，并且能够找到解决 BST 中最大深度问题的有效解决方案，但我不清楚递归是如何工作的，以及每次每次添加 +1 的方式深度水平。考虑这个问题的好方法是什么？基本上每次节点值不为 null 时，1 都会添加到最终将返回调用堆栈的内容中(即在每个级别回溯到根)？

 function maxDepth(node) {
  // console.log(node.left);
  if (node) {
    return Math.max(maxDepth(node.left), maxDepth(node.right)) + 1;
  } else {

    return 0;
  }
}

Answer 1

maxDepth(node) 的代码读起来是这样的:

1. 如果 node不是 null :

   1. 运行同样的算法 maxDepth在 node的左 child 。让这个答案成为x .
   2. 运行同样的算法 maxDepth在 node的右儿。让这个答案成为y .
   3. 计算 Math.max(x, y) + 1 ，并返回此值作为此函数调用的答案。

2. 否则node是null , 然后返回 0 .

---

这意味着当我们尝试计算 maxDepth(node)在非空节点上，我们首先计算 maxDepth()在 node 上的 child ，让这两个子计算完成。然后我们取这些值的最大值，加 1，然后返回结果。

示例:

      a
     / \
    b   f
   / \   \
  c   e   g
 /           
d 

调用堆栈:

a => max(b,f)
b => max(c,e)
c => max(d,null)
d => max(null,null)
d <= (0,0)+1 = 1
c <= (1,0)+1 = 2
e => max(null,null)
e <= (0,0)+1 = 1
b <= (2,1)+1 = 3
f => (null,g)
g => (null,null)
g <= (0,0)+1 = 1
f <= (0,1)+1 = 2
a <= (3,2)+1 = 4