树形机构，怎么反向递归，根据末端子元素状态改变所有父元素的状态

Question

let a = [
{

key: 1,
title: '一级',
parentKey: 0,
status: {choose: false},
children: [
  {
    key: 10, title: '一级-0', parentKey: 1, status: {choose: false}, children: [
      {key: 15, title: '一级-0-1', parentKey: 10, status: {choose: true}}
    ]
  },
  {key: 11, title: '一级-1', parentKey: 1, status: {choose: false}},
  {key: 12, title: '一级-2', parentKey: 1, status: {choose: false}},
  {key: 13, title: '一级-3', parentKey: 1, status: {choose: false}},
  {key: 14, title: '一级-4', parentKey: 1, status: {choose: false}}
]

}
];

这样一个树形结构,怎么写一个反向递归的方法，根据最末端对象的choose字段的状态，改变其所有父级的choose状态（即父元素的children中有子元素的choose状态为true则该父元素的choose状态为true否则为false）

Answer 1

我也写了一版，供参考

function chooseCheck(list) {
  let choosed = false
  ;(list || []).forEach(data => {
    if (data.children && data.children.length > 0) data.status.choose = chooseCheck(data.children)
    if (data.status.choose) choosed = true
  })

  return choosed
}

chooseCheck(dataList)

Answer 2

深度优先很好搞的吧。
对于任何节点都检查子一级的状态来设置自己的状态.
写个思路，没测试：

function checkList (list) {
  list.forEach(item => {
    if (!item.children || !item.children.length) return
    checkList(item.children)
    item.status.choose = item.children.every(child => child.status.choose)
  })
}

Answer 3

反向递归什么的。。。抱歉，算法基础不行，只能正向。
参照 GC 算法中的“标记-清除”法，采用 “净化-标记-污染” 的思路，先假设子树全为 false ，将当前节点净化为 false ，然后标记当前节点(将其记录在数组中)，末端为 true 的话，回溯污染所有带标记的节点，并去除所有标记(将数组清空)，开始下一子树的扫描。
试着写了一下，没有测试，回溯的时候可能会重新净化一些被污染的节点，解决思路是先完全净化一遍(除了末端节点)，再遍历污染一遍。

const parents = [];
function setStatus(list, parents){
    list.forEach(item => {
        // 如果为末节点
        if (!item.children || !item.children.length) {
            const choose = item.choose;
            if(item.choose){
                while(!!parents.length){
                    parents.shift().status.choose = choose;
                }
            } else {
                parents.length = 0;
            }
            return
        }
        
        parents.push(item);
        checkList(item.children, parents);
    })
}

完整递归会比较耗性能，只能用于数据预处理，如果末端节点随时会变化的话，需要考虑更好的算法。