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

Question

我是 JavaScript 中数据结构的新手，正在尝试学习二叉搜索树。我正在关注一个博客 post 并且能够找到解决 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) 的代码如下所示：

如果node不是null:
1. 运行在 node 的左侧 child 使用相同的算法 maxDepth。让这个答案成为 x.
2. 运行在 node 的右侧 child 使用相同的算法 maxDepth。让这个答案成为 y.
3. 计算 Math.max(x, y) + 1，并将此值 return 作为此函数调用的答案。
否则node就是null,那么return0.

这意味着当我们尝试在 non-null 节点上计算 maxDepth(node) 时，我们首先在 node 的两个 children 上计算 maxDepth() ，并让这两个子计算完成。然后我们取这些值的最大值，加 1，return 结果。

示例：

调用堆栈：

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

Answer 2

让我以更简单的方式重写代码，以便于更好地解释。

function maxDepth(node) {
  if (node == null)
      return 0;
  else {
      l = maxDepth(node.left)
      r = maxDepth(node.right)
      return Math.max(left, right) + 1;
  }
}

现在，让我们用下面的树来解释上面的递归：

函数 maxDepth(node) 被根 (A) 调用，因此，我们将从节点 A:

开始以图形方式解释我们的递归堆栈

A
| l = ?
|-------> B
|         | l = ?
|         |-------> D
|         |         | l = ?
|         |         |-------> null (return 0)

A
| l = ?
|-------> B
|         | l = ?
|         |-------> D
|         |         | l = 0 <---------|
|         |         |-------> null (return 0)

A
| l = ?
|-------> B
|         | l = ?
|         |-------> D
|         |         | l = 0 
|         |         |
|         |         | r = ?
|         |         |-------> null (return 0)

A
| l = ?
|-------> B
|         | l = ?
|         |-------> D
|         |         | l = 0 
|         |         |
|         |         | r = 0 <---------|
|         |         |-------> null (return 0)

A
| l = ?
|-------> B
|         | l = ? <--------------------------|
|         |-------> D                        |
|         |         | l = 0                  |
|         |         |          max(0,0)+1 => 1
|         |         | r = 0 


A
| l = ?
|-------> B
|         | l = 1 <--------------------------|
|         |-------> D                        |
|         |         | l = 0                  |
|         |         |          max(0,0)+1 => 1
|         |         | r = 0 


A
| l = ?
|-------> B
|         | l = 1 
|         |
|         | r = ? 
|         | -------> null (return 0)

A
| l = ?
|-------> B
|         | l = 1 
|         |
|         | r = 0 <---------| 
|         | -------> null (return 0)


A
| l = ? <--------------------------|
|-------> B                        |
|         | l = 1                  | 
|         |          max(1,0)+1 => 2
|         | r = 0

A
| l = 2 <--------------------------|
|-------> B                        |
|         | l = 1                  | 
|         |          max(1,0)+1 => 2
|         | r = 0

A
| l = 2 
|
| r = ?        
| -------> C 
|          | l = ? <---------| 
|          |-------> null (return 0)

A
| l = 2 
|
| r = ?        
| -------> C 
|          | l = 0 
|          |
|          | r = ? <---------| 
|          |-------> null (return 0)

A
| l = 2 
|
| r = ? <---------------------------|        
| -------> C                        | 
|          | l = 0                  | 
|          |          max(0,0)+1 => 1
|          | r = 0 

A
| l = 2 
|
| r = 1 <---------------------------|        
| -------> C                        | 
|          | l = 0                  | 
|          |          max(0,0)+1 => 1
|          | r = 0 


A <----------------------|  
| l = 2                  |  
|          max(2,1)+1 => 3
| r = 1

最后，A returns 3.

3
^
|
A (3)<-------------------|  
| l = 2                  |  
|          max(2,1)+1 => 3
| r = 1

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

Explain how recursion works in an algorithm to determine depth of binary tree?

javascript

algorithm

recursion

binary-tree

depth