解释递归在确定二叉树深度的算法中是如何工作的
Explain how recursion works in an algorithm to determine depth of binary tree?
我是JavaScript中数据结构的新手,正在尝试学习二进制搜索树。我一直在关注一篇博客文章,并能够找到在BST中找到最大深度的问题的有效解决方案,但我不清楚递归是如何工作的,也不清楚+1是如何在每个深度级别上每次添加的。思考这个问题的好方法是什么?基本上是不是每次节点值不为空时,都会将1添加到最终将返回到调用堆栈的值中(即,在每个级别上,当它回溯到根时)?
function maxDepth(node) {
// console.log(node.left);
if (node) {
return Math.max(maxDepth(node.left), maxDepth(node.right)) + 1;
} else {
return 0;
}
}
maxDepth(node)
的代码如下所示:
-
如果
node
不是null
:- 在
node
的左子代上运行相同的算法maxDepth
。让这个答案是x
- 在
node
的右子代上运行相同的算法maxDepth
。让这个答案是y
- 计算
Math.max(x, y) + 1
,并返回此值作为此函数调用的答案
- 在
-
否则
node
为null
,则返回0
。
这意味着,当我们试图在非null节点上计算maxDepth(node)
时,我们首先在node
的两个子节点上计算出maxDepth()
,并让这两个子计算完成。然后我们取这些值的最大值,加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
为了便于更好地解释,让我用一种更简单的方式重写代码。
function maxDepth(node) {
if (node == null)
return 0;
else {
l = maxDepth(node.left)
r = maxDepth(node.right)
return Math.max(left, right) + 1;
}
}
现在,让我们用下面的树来解释上面的递归:
A
/ '
B C
/
D
函数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
返回3
。
3
^
|
A (3)<-------------------|
| l = 2 |
| max(2,1)+1 => 3
| r = 1
相关文章:
- Javascript:selenium Web驱动程序isDisplayed()不工作
- jQuery UI自动完成突然停止工作
- AngularJS UI路由器不能像ng路由器那样工作
- HTML5音频加载和播放获胜'我不能在iPad上工作
- JavaScript打印功能使日历停止工作
- Javascript.getHours()工作不正常
- 为什么这在IE中的工作方式与在Firefox中不同
- 视频HTML没有'无法在Internet Explorer 11上工作
- 扩展移相器按钮类不工作
- Firebase迁移-简单的Firebase.set没有'不再工作了——旧的还是新的
- 谷歌地图不是以HTML显示,而是在JS Fiddle上工作
- 正在尝试使用if和else添加类,但无法正常工作
- Jquery FadeIn FadeOut 只工作一次
- Foreach无法在Typescript中工作
- 另一个ajax调用中的Jquery ajax调用在for循环中没有按预期工作
- 为什么不是't窗口.恢复正常工作吗?(javascript/jquery)
- JS可以在Chrome中工作,但不能在Firefox中工作
- ajaxToolkit PopupControlExtender不工作.过时的
- HTML标记在脚本标记中工作
- 在JavaScript中的类中,push和concat的工作方式有何不同