广度优先遍历和深度优先遍历

深度优先遍历

// 递归
function deepTraversal(node, list = []){
    if(!node) return list;
    list.push(node);
    const children = node.children || [];
    children.map(item => deepTraversal(item, list));
    return list
}
// 非递归
function deepTraversal(node){
  if(!node) return []
  const stack = [node]
  const result = []
  while(!!stack.length){
     const item = stack.pop();
     result.push(item)
     const children = item.children || [];
     for(let i = children.length - 1; i >= 0; i--){
          stack.push(children[i])
     }
  }
return result
}

广度优先遍历

// 非递归
function widthTraversal(node){
  if(!node) return []
  const stack = [node]
  const result = []
  while(!!stack.length){
     const item = stack.shift();
     result.push(item)
     const children = item.children || [];
     for(let i = 0; i <children.length; i++){
          stack.push(children[i])
     }
  }
return result
}