最近在找工作，翻看cnode招聘贴的过程中，想起看到的一个非常有意思的题目，特此分享给大家，当然不是为了做题而做题，主要还是给大家分享一下promise的理解和使用。 相信你花一点点时间阅读，会有一定的收获。原题地址

当然， 原题有点啰嗦，为了节约大家的时间， 我把题目做了一个抽象，大概的意思是，服务器上面有一棵树， 树的结构为如下类型

/**
 * tree set example
 * 
 * {
 *  id: 0,
 *  children: [
 *   {
 *     id: 2
 *     children: [{id: 4, children: []}, {id: 5, children: []}],
 *   },
 *   {
 *     id: 3,
 *     children: [{id: 6, children: []}, {id: 7, children: []}],
 *   },
 * ]
 * }

服务器提供了一下api, 能根据 id 取得 这个id对应的子id, 比如 发起 request/id/0 那么服务器返回[2, 3], 即发起0 返回 [2, 3], 发起 2， 返回[4, 5], 然后在客户端必须建立起和服务器一模一样的树，而且根id已知 为0. （加分项，控制并发为5）

如果是同步的情况下， 相信对大多数人来说，不是难题，一个递归就搞定了，而es7 提供了 async 和 await 确实可以怎么做， 代码也比较简单，对于async 和 await的代码我就不贴出了，主要想讲的是 promise 如何在异步递归的场景使用。

请求走的都是get方法， 每次访问服务器返回一个promise， 于是对服务器的模拟如下

function simuServerReturn(ids) {
  return new Promise((res) => {
    setTimeout(res, 3000, ids);
  });
}

function get(id) {
  if (id === 0) return simuServerReturn([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
  if (id === 1) return simuServerReturn([11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]);
  if (id === 3) return simuServerReturn([22, 23, 24, 25, 26, 27, 28]);
  return simuServerReturn([]);
}

服务器对应的树为 tree

还是按照递归的思想， 进行异步编程

var result = {};

// container 为 当前这个id对应的对象
function travel(container, startID) {

  container.id = startID;
  container.children = [];
  //  整体返回一个promise 
  return get(startID).then((ids) => {
    // 并发请求所有孩子
    return Promise.all(ids.map(id => {
      var childContainer = {};
      // 将孩子加入到所属关系中
      container.children.push(childContainer);
      // 对孩子id对象进行属性补充 递归
      return travel(childContainer, id);
    }));
  });
}
// 得到结果
travel(result, 0).then(() => {
  console.log(JSON.stringify(result));
});

上面的 代码其实也比较短，可能很多小伙伴在这里就懵逼了。为何travel().then() 就是得到结果了。 我们可以慢慢分析一下这里算法的正确性和promise执行流程

第一个travel 函数会返回一个promise (即 这个promise实际为 get(0).then 返回的)， 这个promise状态啥时候确定呢？ 它必须等待.then 注册的函数返回的 Promise.all() 这个promise状态确定， Promise.all 又必须等待 .all()里面数组参数中，所有子promsie状态确定，它状态才能确定， 而 每个子promise 即为 递归 travel(childContainer, id) 返回的promsie, 也就是说，上层递归函数 travel(parent) 返回的promise状态必须等待，它里面调用的下层递归的travel(child)返回的promise状态确定， 即

travel(result, 0)  状态确定之时， 已经完成了 子[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 的每个请求，
1的请求成功，也意味着[11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]的每个请求成功，依次类推

所以这道题就轻松的解出来了。 如果搞定加分项呢， 并发那里好像是把 子 id 全部并发出去了，那是不是把 子 id 切割一下， 每5个一组，就可以了呢

// 把数组按照 数目切割成几个子数组
//splitArrayByNum([1, 2, 3, 4], 2) -->[[1, 2], [3, 4]]
function splitArrayByNum(array, num) {
  var tmp = array.slice();
  var result = [];
  while(tmp.length > 0) {
    result.push(tmp.splice(0, num));
  }
  return result;
}
//  这个一个promise 生产函数，为啥会有这个函数出来？
//  实际是为了做promise的串行调用， 我们知道，一个promise一旦
//  生产出来后，它就立即执行了， 为了控制并发，我们只有利用函数延迟执行
//  类似于 thunk思想
// pContainer 为 子id数组ids的 父容器 
function promiseFac(pContainer, ids) {
  return Promise.all(ids.map(id => {
    var childContainer = {};
    pContainer.children.push(childContainer);
    return travel(childContainer, id);
  }));
}

function travel(container, startID) {

  container.id = startID;
  container.children = [];

  return get(startID).then((ids) => {
    // 做prommise串行调用的初始对象
    var result = Promise.resolve();
    // 先对返回的子数组切割， 返回进行串行调用 
    splitArrayByNum(ids, 5).forEach((childIds) => {
      //  为使用参数 外面套了一层function
      result = result.then(() => promiseFac(container, childIds));
    });
    return result;
  });
}

travel(result, 0).then(() => {
  console.log(JSON.stringify(result));
});

这里可能有些人会对 result = result.then(() => promiseFac(container, childIds)); 这句话有些不理解， 其实，为了控制并发，前一个result的状态确定后， 才执行 .then 注册的 () => promiseFac(container, childIds)， 这个函数返回的promise状态确定后， .then本身返回的promise状态才确定，即后一个result状态才确定，依次类推，所以就形成了串行调用。

写到这里以为已经完美了，其实并不是，上面只是想让你们了解一下，promise如何控制串行调用的，上面的代码实际还不能真正控制并发量为5， 虽然我们在同级之间做了并发限制，但是，代码毕竟是深度递归调用的，不同级之间无法控制，既然直接深度遍历无法控制，那么我们就加上一点广度的思路，问题就完美解决了

var result = {id: 0, children: []};
//  利用队列进行存储中间使用的所有对象
var queue = [result];
function travel() {
  if (queue.length > 0) {
    const length = Math.min(5, queue.length);
    const reqObjs = queue.splice(0, length);
    //  这里异步调用很简单， 前一个promise　确定后，才往下递归
    Promise.all(reqObjs.map(req => get(req.id))).then((response) => {
      for (let i = 0; i < response.length; i++) {
        for (let j = 0; j < response[i].length; j++) {
          const childrenContainer = {id: response[i][j], children: []};
          reqObjs[i].children.push(childrenContainer);
          queue.push(childrenContainer);
        }
      }
      travel();
    });
  // 队列里面没有东西了， 自然就结束了
  } else {
    console.log(JSON.stringify(result));
  }
}

travel();

async 版本和所有代码 都在github