以下代码结果运行结果是什么?为什么?
let cache,
result = Infinity;
function fun(tree) {
if (!tree) return;
fun(tree.left);
if (cache) {
result = Math.min(result, Math.abs(cache - tree.value));
}
cache = tree.value;
fun(tree.right);
}
const tree = {
value: 90,
left: {
value: 50,
left: {
value: 20,
left: {
value: 5,
left: null,
right: null
},
right: {
value: 25,
left: null,
right: null
}
},
right: {
value: 75,
left: {
value: 66,
left: null,
right: null
},
right: {
value: 80,
left: null,
right: null
}
}
},
right: {
value: 150,
left: {
value: 95,
left: {
value: 92,
left: null,
right: null
},
right: {
value: 111,
left: null,
right: null
}
},
right: {
value: 175,
left: {
value: 166,
left: null,
right: null
},
right: {
value: 200,
left: null,
right: null
}
}
}
};
fun(tree);
console.log(result);
###
猜一遍,跑一遍,搞不懂,跟一遍
补充 [2020-05-07 23:32:17]
上面是之前的回答。还是正儿八经回答一下吧。不是直接的答案,是方法:
这个问题的关键在于 fun()
函数,这个函数是一个递归调用函数。递归一般按照数学归纳法来思考,如果忘了这个方法,可以先去复习一下。
关于递归,要注意两个要点:
递归是一个循环往复的处理过程,它有两个点需要注意:
- 递归调用点,递归调用自己(或另一个可能会调用自己的函数)
- 递归结束点,退出当前函数
来分析一下 fun
函数,可以发现
function fun(tree) {
if (!tree) return;
// ^^^^^^^^^^^^^^^^^^ 结束点
fun(tree.left);
// ^^^^^^^^^^^^^^^ 调用点①
if (cache) {
result = Math.min(result, Math.abs(cache - tree.value));
}
cache = tree.value;
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// 以上 4 行是计算过程
fun(tree.right);
// ^^^^^^^^^^^^^^^^ 调用点②
}
递归函数处理的,都是具有相似特性的数据结构,在这个例子中,是一个树的节点,它的结构是这样的
- value: 值
- left: 左节点,可能为 null
- right: 右节点,可能为 null
而 fun
已经描述了对其中一个节点的处理过程:
先处理左支(递归),再处理数据(计算),再处理右支(递归)
两个分支的处理是递归调用点,它们的处理过程和当前节点一模一样(都是 fun
函数,能不一样吗),所以只要把当前节点处理好的,其他的都不在话下
这里还缺个结束点,怎么找?
很容易明白,left
、right
为 null
的时候就是结束点,所以可以在 fun(tree.left)
之前判断(以左为例,右相同),比如
if (tree.left) { fun(tree.left); }
这样,只要 left
为空,就不会递归调用,只要当前函数这次执行完成都没有递归调用,就结束了(结束点找到了)。right
相同。
或者,也可以换个思维,反正对 left
和 right
都要调用 fun()
,它们为作为形参 tree
传入,那一开始就判断 tree
是否为 null
就只需要一次判断就行,也就是例中的首行:
if (!tree) return;
如果 tree
为空,直接退出函数,函数本次执行没有进行任何递归调用即结束,结束点在这里。
上面用两种方法找到了结束点,结束点略有不同,但作用一样。区别就在于一个多写两个判断,另一个多调一次 fun()
。
前面把道理讲完了,接下来完全可以在脑袋里模拟运行(如果空间想像能力略差,那就调试模式下跟一遍):
我给前面几个节点的处理步骤,大概是这样:
() → 90left → 50left → 20left → 5left↙(null)
5value → 5right↙(null)
↙(完成5节点)
20value → 20right → 25left → ...
###
90left
表示值为 90 的那个节点5value
表示计算值为 5 的那个节点(前面提到的 4 行计算)↙
符号显然就是递归结束点,后面的括号说明了结束原因
好像回到了当年百度知道上面帮人做作业。