使用递归js在树状对象中查找最小值和最大值

Question

我正在尝试使用递归在树状对象中查找最小值和最大值，但我实际上不明白如何找到这些值。此外，我的函数必须是纯函数，我不能使用循环或 forEach。只有 map、reduce、filter 可用。这就是我的数据的样子：

const tree = {
children: [ 
    { 
        children: [
            { 
                children: [],
                values: [15.667786122807836]
            }
        ],
        values: [35.77483035532576, 1.056418140526505]
    },
    {
        children: [
            {
                children: [
                    {
                        children: [],
                        values: [67.83058067285563]
                    }
                ],
                values: [98.89823527559626]
            }
        ],
        values: [51.49890385802418, 41.85766285823911]
    },
],
values: [6.852857017193847, 28.110428400306265, 51.385186145220494]};

我正在尝试做这样的事情：

const min = graph => {
if (!graph.children.length && !graph.values.length) return;

if (!graph.children.length && graph.values.length) {
    return Math.min(...graph.values);
}

return graph.children.map(el => {
    const minValue = Math.min(...el.values);
    min(el);
    return minValue;
});

};

但这不是很好用。所以任何人都可以解释调用堆栈的工作原理，也许给我一些很好的例子，并解释如何解决我的问题。感谢您的帮助，抱歉英语不好）。哦，还有））如何获得不同深度级别的两个节点之间的距离？

Answer 1

我不是 JS 程序员，但我一直在寻求练习。这是我想出的：

const tree = {
  children: [{
      children: [{
        children: [],
        values: [15.667786122807836]
      }],
      values: [35.77483035532576, 1.056418140526505]
    },
    {
      children: [{
        children: [{
          children: [],
          values: [67.83058067285563]
        }],
        values: [98.89823527559626]
      }],
      values: [51.49890385802418, 41.85766285823911]
    },
  ],
  values: [6.852857017193847, 28.110428400306265, 51.385186145220494]
};

function treeMin(graph) {
  if (graph.children.length == 0) return Math.min(...graph.values);
  return Math.min(...graph.values,
                  graph.children.reduce((prev, cur) =>
                     Math.min(prev, treeMin(cur)), Number.MAX_SAFE_INTEGER
                  ));
}

console.log(treeMin(tree));

我给函数起了一个名字来进行递归调用。它做的第一件事是检查是否没有 children。如果不是，它只是 return 值的最小值。

如果有children，return的最小值和children调用reduce的结果。在 reduce 内部进行递归调用。

注意：不处理values为空的情况。这可以很容易地添加。

Answer 2

通常对于家庭作业问题，我会提示与 OP 进行更多对话，但由于这已经有一个有效的、可接受的答案，我将添加一个更简单的答案：

const min = ({values = [], children = []}) => 
  Math .min (...values, ... children .map (min))

const tree = {children: [{children: [{children: [], values: [15.667786122807836]}], values: [35.77483035532576, 1.056418140526505]}, {children: [{children: [{children: [], values: [67.83058067285563]}], values: [98.89823527559626]}], values: [51.49890385802418, 41.85766285823911]}, ], values: [6.852857017193847, 28.110428400306265, 51.385186145220494]};

console .log (min (tree))

我们只使用 Math.min，将当前值和对其每个子项的递归调用结果传播到它的参数中。我们将 values 和 children 都默认为空数组，以防任何一个节点丢失。

显然 max 是对此的微不足道的更改。

使用递归js在树状对象中查找最小值和最大值

Find minimal and maximum values in a tree like object using recursion js

javascript

recursion

binary-tree

data-structures