将最大值传播到嵌套树中的父节点 javascript

Question

具有如下所示的嵌套数组：

[
    {
        "id": 100,
        "idParent": null,
        "anidatedView": null,
        "state": null,
        "warningHighThreshold": null,
        "dangerHighThreshold": null,
        "lvl": 1,
        "children": [
            {
                "id": 139,
                "idParent": 100,
                "anidatedView": null,
                "state": null,
                "warningHighThreshold": null,
                "dangerHighThreshold": null,
                "lvl": 2,
                "children": [
                    {
                        "id": 186,
                        "idParent": 139,
                        "anidatedView": 279,
                        "state": 15.58,
                        "warningHighThreshold": 80,
                        "dangerHighThreshold": 100,
                        "lvl": 3,
                        "children": []
                    },
                    {
                        "id": 189,
                        "idParent": 139,
                        "anidatedView": 193,
                        "state": 40.65,
                        "warningHighThreshold": 80,
                        "dangerHighThreshold": 100,
                        "lvl": 3,
                        "children": []
                    }
                ]
            },
            {
                "id": 140,
                "idParent": 100,
                "anidatedView": null,
                "state": null,
                "warningHighThreshold": null,
                "dangerHighThreshold": null,
                "lvl": 2,
                "children": [
                    {
                        "id": 193,
                        "idParent": 140,
                        "anidatedView": 183,
                        "state": 65.41,
                        "warningHighThreshold": 92,
                        "dangerHighThreshold": 100,
                        "lvl": 3,
                        "children": []
                    }
                ]
            },
            {
                "id": 141,
                "idParent": 100,
                "anidatedView": null,
                "state": null,
                "warningHighThreshold": null,
                "dangerHighThreshold": null,
                "lvl": 2,
                "children": [
                    {
                        "id": 194,
                        "idParent": 141,
                        "anidatedView": 143,
                        "state": 60.77,
                        "warningHighThreshold": 90,
                        "dangerHighThreshold": 100,
                        "lvl": 3,
                        "children": []
                    },
                    {
                        "id": 195,
                        "idParent": 141,
                        "anidatedView": 436,
                        "state": 59.13,
                        "warningHighThreshold": 90,
                        "dangerHighThreshold": 100,
                        "lvl": 3,
                        "children": []
                    }
                ]
            }
        ]
    }
]

我正在尝试将状态的最大值（还有该最大节点的 warningHighThreshold 和 dangerHighThreshold）传播到所有父节点。
状态和阈值将始终在树的最后一级可用。

知道如何用递归来做到这一点吗？

提前致谢！

Answer 1

我终于设法解决了这个问题。我的解决方案留给可能有同样问题的人。

const populateState = item => {
  if (item.children.length) {
    const maxValue = item.children
      .map(child => populateState(child))
      .filter(({ state }) => state != null)
      .reduce((maxValue, value) => (value.state > maxValue.state ? value : maxValue), { state: -1 })
    item.state = maxValue.state
    item.warningHighThreshold = maxValue.warningHighThreshold
    item.dangerHighThreshold = maxValue.dangerHighThreshold
    return maxValue
  } else {
    const { state, warningHighThreshold, dangerHighThreshold } = item
    return { state, warningHighThreshold, dangerHighThreshold }
  }
}

用法：
（array 变量是我在问题中定义的列表）

populateState({ children: array})

欢迎任何代码增强。

Answer 2

试试这个：

const list = JSON.parse(`[
    {
        "id": 100,
        "idParent": null,
        "anidatedView": null,
        "state": null,
        "warningHighThreshold": null,
        "dangerHighThreshold": null,
        "lvl": 1,
        "children": [
            {
                "id": 139,
                "idParent": 100,
                "anidatedView": null,
                "state": null,
                "warningHighThreshold": null,
                "dangerHighThreshold": null,
                "lvl": 2,
                "children": [
                    {
                        "id": 186,
                        "idParent": 139,
                        "anidatedView": 279,
                        "state": 15.58,
                        "warningHighThreshold": 80,
                        "dangerHighThreshold": 100,
                        "lvl": 3,
                        "children": []
                    },
                    {
                        "id": 189,
                        "idParent": 139,
                        "anidatedView": 193,
                        "state": 40.65,
                        "warningHighThreshold": 80,
                        "dangerHighThreshold": 100,
                        "lvl": 3,
                        "children": []
                    }
                ]
            },
            {
                "id": 140,
                "idParent": 100,
                "anidatedView": null,
                "state": null,
                "warningHighThreshold": null,
                "dangerHighThreshold": null,
                "lvl": 2,
                "children": [
                    {
                        "id": 193,
                        "idParent": 140,
                        "anidatedView": 183,
                        "state": 65.41,
                        "warningHighThreshold": 92,
                        "dangerHighThreshold": 100,
                        "lvl": 3,
                        "children": []
                    }
                ]
            },
            {
                "id": 141,
                "idParent": 100,
                "anidatedView": null,
                "state": null,
                "warningHighThreshold": null,
                "dangerHighThreshold": null,
                "lvl": 2,
                "children": [
                    {
                        "id": 194,
                        "idParent": 141,
                        "anidatedView": 143,
                        "state": 60.77,
                        "warningHighThreshold": 90,
                        "dangerHighThreshold": 101,
                        "lvl": 3,
                        "children": []
                    },
                    {
                        "id": 195,
                        "idParent": 141,
                        "anidatedView": 436,
                        "state": 59.13,
                        "warningHighThreshold": 90,
                        "dangerHighThreshold": 100,
                        "lvl": 3,
                        "children": []
                    }
                ]
            }
        ]
    }
]`);

function getHigh(obj, prop)
{
  let ret = null;
  for(let n = 0; n < 2; n++)
  {
    for(let i = 0; i < obj.length; i++)
    {
      const r = getHigh(obj[i].children, prop);
      if (r > obj[i][prop])
      {
        obj[i][prop] = r;
        ret = r;
      }

      if (obj[i][prop] > ret)
        ret = obj[i][prop];
    }
  }
  return ret;
}

console.log("warningHighThreshold", getHigh(list, "warningHighThreshold"));
console.log(JSON.stringify(list, null, 2));
console.log("dangerHighThreshold", getHigh(list, "dangerHighThreshold"));
console.log(JSON.stringify(list, null, 2));

Answer 3

这种问题可以用深度优先搜索来解决...

let input = [{ "id": 100, "idParent": null, "anidatedView": null, "state": null, "warningHighThreshold": null, "dangerHighThreshold": null, "lvl": 1, "children": [{ "id": 139, "idParent": 100, "anidatedView": null, "state": null, "warningHighThreshold": null, "dangerHighThreshold": null, "lvl": 2, "children": [{ "id": 186, "idParent": 139, "anidatedView": 279, "state": 15.58, "warningHighThreshold": 80, "dangerHighThreshold": 100, "lvl": 3, "children": [] }, { "id": 189, "idParent": 139, "anidatedView": 193, "state": 40.65, "warningHighThreshold": 80, "dangerHighThreshold": 100, "lvl": 3, "children": [] }] }, { "id": 140, "idParent": 100, "anidatedView": null, "state": null, "warningHighThreshold": null, "dangerHighThreshold": null, "lvl": 2, "children": [{ "id": 193, "idParent": 140, "anidatedView": 183, "state": 65.41, "warningHighThreshold": 92, "dangerHighThreshold": 100, "lvl": 3, "children": [] }] }, { "id": 141, "idParent": 100, "anidatedView": null, "state": null, "warningHighThreshold": null, "dangerHighThreshold": null, "lvl": 2, "children": [{ "id": 194, "idParent": 141, "anidatedView": 143, "state": 60.77, "warningHighThreshold": 90, "dangerHighThreshold": 100, "lvl": 3, "children": [] }, { "id": 195, "idParent": 141, "anidatedView": 436, "state": 59.13, "warningHighThreshold": 90, "dangerHighThreshold": 100, "lvl": 3, "children": [] }] }] }]
let keys = ["state", "warningHighThreshold", "dangerHighThreshold"];

function populateState(children) {
    for (let item of children)
        Object.assign(item, populateState(item.children))

    return children.length
        ? Object.assign(...keys.map(k => ({ [k]: Math.max(...children.map(o => o[k])) })))
        : {}
}

console.log("Max Threshold:", populateState(input), "\n\nInput:", input)

Answer 4

更新

一条评论指出了一项缺失的要求。我们应该从中找到具有最大值 state 和 select 的其他两个值的后代对象，而不是捕获具有独立最大值的 state warningHighThreshold 和 dangerHighThreshhold那个对象。这是一个满足该要求的版本。

const collect = (o) => {
  const kids = (o .children || []) .map (collect)
  const highest = [o, ...kids] .reduce (
    (a, x) => x.state > a.state ? x : a, 
    {state: -Infinity}
  )
  return {
    ...o,
    state: highest .state,
    warningHighThreshold: highest .warningHighThreshold,
    dangerHighThreshold: highest .dangerHighThreshold,
    children: kids,
  }
}

const collectMax = (list) => 
  list .map (collect)

const input = [{id: 100, idParent: null, anidatedView: null, state: null, warningHighThreshold: null, dangerHighThreshold: null, lvl: 1, children: [{id: 139, idParent: 100, anidatedView: null, state: null, warningHighThreshold: null, dangerHighThreshold: null, lvl: 2, children: [{id: 186, idParent: 139, anidatedView: 279, state: 15.58, warningHighThreshold: 80, dangerHighThreshold: 100, lvl: 3, children: []}, {id: 189, idParent: 139, anidatedView: 193, state: 40.65, warningHighThreshold: 80, dangerHighThreshold: 100, lvl: 3, children: []}]}, {id: 140, idParent: 100, anidatedView: null, state: null, warningHighThreshold: null, dangerHighThreshold: null, lvl: 2, children: [{id: 193, idParent: 140, anidatedView: 183, state: 65.41, warningHighThreshold: 92, dangerHighThreshold: 100, lvl: 3, children: []}]}, {id: 141, idParent: 100, anidatedView: null, state: null, warningHighThreshold: null, dangerHighThreshold: null, lvl: 2, children: [{id: 194, idParent: 141, anidatedView: 143, state: 60.77, warningHighThreshold: 90, dangerHighThreshold: 101, lvl: 3, children: []}, {id: 195, idParent: 141, anidatedView: 436, state: 59.13, warningHighThreshold: 90, dangerHighThreshold: 100, lvl: 3, children: []}]}]}]


console .log (collectMax (input))

.as-console-wrapper {max-height: 100% !important; top: 0}

原回答

这是一个非变异版本，它似乎可以满足您的要求，返回一个新对象，其最大值汇总到其祖先：

const collectMax = (xs) => xs .map (({children, kids = collectMax (children), ...rest}) => ({
  ...rest,
  state: Math.max (rest.state, ... kids .map (k => k .state)),
  warningHighThreshold: Math .max (rest .warningHighThreshold, ... kids .map (k => k .warningHighThreshold)),
  dangerHighThreshold: Math .max (rest. dangerHighThreshold, ... kids .map (k => k .dangerHighThreshold)),
  children: kids
}))

const list = [{id: 100, idParent: null, anidatedView: null, state: null, warningHighThreshold: null, dangerHighThreshold: null, lvl: 1, children: [{id: 139, idParent: 100, anidatedView: null, state: null, warningHighThreshold: null, dangerHighThreshold: null, lvl: 2, children: [{id: 186, idParent: 139, anidatedView: 279, state: 15.58, warningHighThreshold: 80, dangerHighThreshold: 100, lvl: 3, children: []}, {id: 189, idParent: 139, anidatedView: 193, state: 40.65, warningHighThreshold: 80, dangerHighThreshold: 100, lvl: 3, children: []}]}, {id: 140, idParent: 100, anidatedView: null, state: null, warningHighThreshold: null, dangerHighThreshold: null, lvl: 2, children: [{id: 193, idParent: 140, anidatedView: 183, state: 65.41, warningHighThreshold: 92, dangerHighThreshold: 100, lvl: 3, children: []}]}, {id: 141, idParent: 100, anidatedView: null, state: null, warningHighThreshold: null, dangerHighThreshold: null, lvl: 2, children: [{id: 194, idParent: 141, anidatedView: 143, state: 60.77, warningHighThreshold: 90, dangerHighThreshold: 101, lvl: 3, children: []}, {id: 195, idParent: 141, anidatedView: 436, state: 59.13, warningHighThreshold: 90, dangerHighThreshold: 100, lvl: 3, children: []}]}]}]

console .log (
  collectMax (list)
)

.as-console-wrapper {max-height: 100% !important; top: 0}

我们首先将函数递归地应用到 children 节点，然后将我们的测试值与每个子节点的适当值结合起来，取最大值，将最大值分配给当前对象以用于适当的属性.

但我认为从中提取辅助函数会更清晰：

const collect = (ps, o, k) => Object.assign (... ps .map (p => ({
  [p]: Math.max (o [p], ... k .map (k => k [p]))
})))

const collectMax = (xs) => xs .map (({children, kids = collectMax (children), ...rest}) => ({
  ... rest,
  ... collect (['state', 'warningHighThreshold', 'dangerHighThreshold'], rest, kids),
  children: kids
}))

这做同样的事情，但稍微简化了代码并使得添加新的最大值属性变得微不足道。

将最大值传播到嵌套树中的父节点 javascript

Propagate max value to parent nodes in nested tree javascript

javascript

recursion

nested-lists

更新

原回答