javascript关于树的题目

Question

以下代码结果运行结果是什么？为什么？

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);

Answer 1

猜一遍，跑一遍，搞不懂，跟一遍

---

补充 [2020-05-07 23:32:17]

上面是之前的回答。还是正儿八经回答一下吧。不是直接的答案，是方法：

这个问题的关键在于 fun() 函数，这个函数是一个递归调用函数。递归一般按照数学归纳法来思考，如果忘了这个方法，可以先去复习一下。

关于递归，要注意两个要点：

递归是一个循环往复的处理过程，它有两个点需要注意：

• 递归调用点，递归调用自己（或另一个可能会调用自己的函数）
• 递归结束点，退出当前函数

来自: 使用递归遍历并转换树形数据（以 TypeScript 为例）

来分析一下 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 行计算）
• ↙ 符号显然就是递归结束点，后面的括号说明了结束原因