寻找红苹果

秋天到了，苹果熟了，因为日照的不同，有的苹果红了，有的还是绿的。作为一个果农，想要找到红苹果，有什么好办法呢？

就像图中的这棵树：

🌿：代表了枝干

🍏：绿苹果代表尚未成熟的果子

🍎：红苹果代表可以采摘的果子

数字：表示序号

现在要帮果农数一下有多少个红苹果，并记录下寻找的路径

比如第一个枝桠上有2个，记录为：[1,4],[1,5]

你有什么好办法吗？

常规我们逐层数就可以了，但是如果这棵树是100层的大树呢？如果要数一个果园呢？

一般我们会将这棵树抽象为一个结构，就用tree来代称

枝桠的结构为{ id:序号, children:代表果子,parentId:他的上级序号 }

苹果的结构为:{ id:序号，color:代表了颜色 }

根据图片，抽象得出的结构为

tree = [
  {
    id: 1,
    parentId: 0,
    children: [
      {
        id: 4,
        color: 'red',
        parentId: 1,
      },
      {
        id: 5,
        color: 'red',
        parentId: 1,
      },
      {
        id: 6,
        color: 'green',
        parentId: 1,
      },
    ]
  },
  {
    id: 2,
    parentId:0,
    children: [
      {
        id: 7,
        parentId: 2,
        children: [
          {
            id: 12,
            color: 'green',
            parentId: 7,
          },
          {
            id: 13,
            color: 'red',
            parentId: 7,
          },
          {
            id: 14,
            color: 'green',
            parentId: 7,
          },
          {
            id: 15,
            color: 'green',
            parentId: 7,
          },
          {
            id: 16,
            color: 'red',
            parentId: 7,
          },
          {
            id: 17,
            color: 'red',
            parentId: 7,
          },
        ]
      },
    ]
  },
  {
    id: 3,
    parentId: 0,
    children: [
      {
        id: 8,
        color: 'green',
        parentId: 3,
      },
      {
        id: 9,
        color: 'red',
        parentId: 3,
      },
      {
        id: 10,
        color: 'green',
        parentId: 3,
      },
      {
        id: 11,
        color: 'red',
        parentId: 3,
      },
    ]
  },
]

我们需要从这个抽象树中，找到红色的果子

因此我们需要一个值path=[],用于记录寻找的路径

一颗我们即将要遍历的树：tree

一个用于存储路径的结果：result

一个配置项：config，因为果农是善变的，可能前5分钟想要的是红苹果数，后5分钟想要的是绿苹果数，所以我们给他做成可配置的

一个用于记录深度：deep

function getAppleTree(path = [], tree = [], result = [], config={ key: 'red'},deep=0) {
  tree.forEach(item => {
    if(path[path.length - 1] !== item.parentId){
       //因为采用的是深度遍历，当从下一级返回到上一级时，deep需要减一，path需要重置
       //重置的逻辑为从path的第0个到当前层级减一
       //如果deep为零，则path是[]
       if(deep>0) {
         deep--;
         path = path.slice(0, deep)
       }
       else {
         path = []
       }
    }
    
    if(item.children && item.children.length>0) {
      path.push(item.id)
      deep++
      getAppleTree(path, item.children, result, config, deep)
    }
    else {
      if(item.color === config.key) {
        const array = [...path, item.id]
        result.push(array)
      }
    }
  })
}

const result = []
getAppleTree([], tree, result, config={key:'red'},0)

//result结果为
[
  [ 1, 4 ],
  [ 1, 5 ],
  [ 2, 7, 13 ],
  [ 2, 7, 16 ],
  [ 2, 7, 17 ],
  [ 3, 9 ],
  [ 3, 11 ]
]

整个逻辑的重点是path的重置

哪怕让我们数整个果园也没关系，你学费了吗？