如何用递归和辅助函数来理解scope/closure？

Question

以下是带有简单问题的示例：

示例 1：查找二叉树的最大深度。

我答对了，但不知道为什么我原来的错误答案是错误的。

正确答案：

var maxDepth = function(root) {
    if (root === null) return 0;
    var maxDepth = 1;
    maxDepth = maxDepthHelper(root, 1, maxDepth);
    return maxDepth;
};

function maxDepthHelper(tree, depth, maxDepth) {
    if (tree.left === null && tree.right === null) {
        maxDepth = depth > maxDepth ? depth : maxDepth;
        return maxDepth;
    }
    if (tree.left) {
    maxDepth = maxDepthHelper(tree.left, depth + 1, maxDepth);
    }
    if (tree.right) {
    maxDepth = maxDepthHelper(tree.right, depth + 1, maxDepth);
    }
    return maxDepth;
}

错误答案：

var maxDepth = function(root) {
    if (root === null) return 0;
    var maxDepth = 1;
    maxDepthHelper(root, 1, maxDepth);
    return maxDepth;
};

function maxDepthHelper(tree, depth, maxDepth) {
    if (tree.left === null && tree.right === null) {
        maxDepth = depth > maxDepth ? depth : maxDepth;
        return;
    }
    if (tree.left) {
        maxDepthHelper(tree.left, depth + 1, maxDepth);
    }
    if (tree.right) {
        maxDepthHelper(tree.right, depth + 1, maxDepth);
    }
}

这与我认为 maxDepth 应该由辅助函数更改有关，最终当我 return 它应该 return 更改但它没有。它只是 returns 1 这是我分配给它的原始内容。但是在下面的示例中，我可以在辅助函数中更改来自父级的变量，那么我在这里缺少什么？

示例2：给定一棵二叉搜索树，编写一个函数kthSmallest，找出其中第k小的元素。

解决方案：

var kthSmallest = function(root, k) {
    let smallestArr = [];
    kthSmallestHelper(root, k, smallestArr);
    return smallestArr.pop()
};

function kthSmallestHelper(bst, k, array) {
    if (bst === null) return;
    kthSmallestHelper(bst.left, k, array);
    if (array.length === k) return;
    array.push(bst.val);
    kthSmallestHelper(bst.right, k, array);
}

Answer 1

在第二个程序中，maxDepth 是一个数字，按值（复制）传递，而不是按引用传递。递归调用实际上是 no-ops，它们的 return 值会立即被丢弃。对于学习不同变量类型如何从一个函数传递到另一个函数的初学者来说，这是一个常见的错误。

也就是说，递归是一种函数式继承，因此将它与函数式风格一起使用会产生最好的结果。这意味着要避免突变和变量重新分配等副作用。您可以大大简化您的 depth 程序 -

function depth(tree)
{ if (tree == null)
    return 0
  else
    return 1 + max(depth(tree.left), depth(tree.right))
}

function max (a, b)
{ if (a > b)
    return a
  else
    return b
}

通常首选 expression-based 语法，因为表达式求值为值，而语句（如 if 和 return）不会 -

const depth = tree =>
  tree == null
    ? 0
    : 1 + max(depth(tree.left), depth(tree.right))

const max = (a, b) =>
  a > b
    ? a
    : b

您的 kthSmallest 程序更难，但 JavaScript 的 imperative-style 生成器可以快速解决问题。使用了突变 k-- 但无法从函数外部观察到 -

function *inorder (tree)
{ if (tree == null) return
  yield* inorder(tree.left)
  yield tree.val
  yield* inorder(tree.right)
}

function kthSmallest (tree, k)
{ for (const v of inorder(tree))
    if (k-- == 0)
      return v
}

本程序纯表达形式略有不同-

const inorder = tree =>
  tree == null
    ? []
    : [ ...inorder(tree.left), tree.val, ...inorder(tree.right) ]

const kthSmallest = (tree, k) =>
  inorder(tree)[k]

这是一个功能演示 -

import { depth, fromArray, inorder, kthSmallest } from "./Tree"

const rand = _ =>
  Math.random() * 100 >> 0

const t =
  fromArray(Array.from(Array(10), rand))

console.log("inorder:", Array.from(inorder(t)))
console.log("depth:", depth(t))
console.log("0th:", kthSmallest(t, 0))
console.log("1st:", kthSmallest(t, 1))
console.log("2nd:", kthSmallest(t, 2))
console.log("99th:", kthSmallest(t, 99))

输出-

inorder: [ 12, 14, 25, 44, 47, 53, 67, 70, 85, 91 ]
depth: 5
0th: 12
1st: 14
2nd: 25
99th: undefined

像下面的 Tree 这样编写模块是分离关注点和组织代码的好习惯 -

// Tree.js

const empty =
  null

const node = (val, left = empty, right = empty) =>
  ({ val, left, right })

const fromArray = (a = []) =>
  a.length < 1
    ? empty
    : insert(fromArray(a.slice(1)), a[0])

const insert = (t = empty, v = null) =>
  t === empty
    ? node(v)
: v < t.val
    ? node(t.val, insert(t.left, v), t.right)
: v > t.val
    ? node(t.val, t.left, insert(t.right, v))
: t

const depth = (tree = empty) => ...

const inorder = (tree = empty) => ...

const kthSmallest = (tree = empty, k = 0) => ...

export { depth, empty, fromArray, inorder, kthSmallest, node }

展开下面的代码片段以在您自己的浏览器中验证结果 -

const empty =
  null

const node = (val, left = empty, right = empty) =>
  ({ val, left, right })

const fromArray = (a = []) =>
  a.length < 1
    ? empty
    : insert(fromArray(a.slice(1)), a[0])

const insert = (t = empty, v) =>
  t === empty
    ? node(v)
: v < t.val
    ? node(t.val, insert(t.left, v), t.right)
: v > t.val
    ? node(t.val, t.left, insert(t.right, v))
: t

const inorder = (tree = empty) =>
  tree === empty
    ? []
    : [ ...inorder(tree.left), tree.val, ...inorder(tree.right) ]

const kthSmallest = (tree = empty, k = 0) =>
  inorder(tree)[k]

const depth = (tree = empty) =>
  tree == null
    ? 0
    : 1 + Math.max(depth(tree.left), depth(tree.right))

const rand = _ =>
  Math.random() * 100 >> 0

const t =
  fromArray(Array.from(Array(10), rand))

console.log("inorder:", JSON.stringify(Array.from(inorder(t))))
console.log("depth:", depth(t))
console.log("0th:", kthSmallest(t, 0))
console.log("1st:", kthSmallest(t, 1))
console.log("2nd:", kthSmallest(t, 2))
console.log("99th:", kthSmallest(t, 99))

Answer 2

函数maxDepth（不幸的命名）中的变量maxDepth（我们称其为外部maxDepth）存储一个值（数字1）。当你调用maxDepthHelper(root, 1, maxDepth)时，传入值1并存储在maxDepthHelper内部的局部变量maxDepth中。我们可以给局部maxDepth赋值，但不会影响外部maxDepth中存储的值，因为它们是两个不同的变量。

函数kthSmallest中的变量smallestArr存储了一个值；该值是指向空数组的指针（内存位置）。当调用 kthSmallestHelper(root, k, smallestArr) 时，就像以前一样，该值（指针）被传入并存储在 kthSmallestHelper 中的局部变量 array 中。实际上，现在 array 和 smallestArr 都存储了指向同一个空数组的指针（内存位置）。如果我们现在对 array 进行任何赋值，比如 array=['some new arr']，变量 smallestArr 将不会受到影响。但是当你调用一个变异方法时，比如 array.push(bst)，发生的事情是 Javascript 引擎查看存储在 array 中的指针，并修改存储在该内存位置的数组。因为 smallestArr 存储指向这个修改后的数组的指针，所以如果调用 smallestArr.pop()，Javascript 引擎将弹出修改后的数组的最后一项。

重要的是要记住任何时候你写一个像 let x = /* some array or object */ 这样的表达式，一个 array/object 被创建，然后一个指向那个 array/object 的指针被存储在变量中。如果写成let x = /* some primitive value (like 3)*/，则直接把值3存入变量

如何用递归和辅助函数来理解scope/closure？

How to understand scope/closure with recursion and helper function?

javascript

algorithm

recursion

binary-tree

data-structures