不使用递归，深度优先，将树转成数组

Question

var arr = [
  {
    name: "a",
    children: [
      {
        name: "a1",
      },
      { name: "a2" },
    ],
  },
  {
    name: "b",
    children: [
      {
        name: "b1",
        children: [
          {
            name: "b11",
            children: [
              {
                name: "b111",
              },
              {
                name: "b12312",
              },
            ],
          },
        ],
      },
    ],
  },
];

期望：

[{
name: "a"
},{
name: "a1"
},{
name: "a2"
},{
name: "b"
},{
name: "b1"
},{
name: "b11"
},{
name: "b111"
}, {
name: "b12312"
}]

要求：

不适用递归

目前思考如下：（还没成功）

while + 栈

function each(tree) {
  const result = [];
  let index = 0;
  let children = tree;

  const stack = [];

  while (children[index]) {
    const child = children[index];
    result.push(child);
    if (Array.isArray(child.children)) {
      stack.push({
        children,
        index,
      });
      children = child.children;
      index = 0;
    } else {
      index++;
      if (!children[index] && stack.length) {
        const next = stack.pop();
        children = next.children;
        index = next.index + 1;
      }
    }
  }

  return result;
}

可行性答案 1

function each(tree) {
  const result = [];
  let index = 0;
  let children = tree;

  const stack = [];
  stack.push({
    children,
    index,
  });

  while (children[index] || stack.length) {
    const child = children[index];
    if (child) {
      result.push(child);
    } else {
      const next = stack.pop();
      children = next.children;
      index = next.index + 1;
      continue;
    }

    if (Array.isArray(child.children)) {
      stack.push({
        children,
        index: index,
      });

      children = child.children;
      index = 0;
    } else {
      index++;
    }
  }

  return result;
}

Answer 1

function treeToList (tree) {
  const result = [...tree];
  for (let i = 0; i < result.length; i++) {
    result[i].children && result.splice(i+1, 0, ...result[i].children)
  }
  return result
}

Answer 2

基于你的思路改造了下：

function each(tree) {
  const result = []
  let index = 0
  let children = tree

  const stack = []

  while (children[index]) {
    const child = children[index]
    result.push(child)

    // 有下级时遍历下级节点
    if (Array.isArray(child.children) && child.children.length) {
      // 记录下级节点遍历完成后需要返回的上一级的下一个节点
      const next = children[index + 1]
      next && stack.push(next)

      children = child.children
      index = 0

      continue
    }

    // 遍历完当前的同级节点
    if (index !== children.length -1) {
      index++
      continue
    }

    // 同级节点遍历完时查看是否有需要返回的上级节点，继续遍历
    const next = stack.length && stack.pop()
    if (next) {
      children = [next]
      index = 0
      continue
    }

    break
  }

  return result
}

但是可读性没有你评论里的好，不过好处是减少了插入子级的过程

Answer 3

arr.reduce((newArr, item) => {
  const stack = [];
  let currentItem = item;
  while(currentItem) {
    const {children, ...other} = currentItem;
    newArr.push(other);
    if (children && children.length) {
      stack.unshift(...children);
    }
    currentItem = stack.shift();
  }
  return newArr;
}, []);

Answer 4

用循环的话就像下面这样：

function dfs(list) {
  const result = []
  const stack = []
  list.forEach(node => {
    stack.push(node)
    while(stack.length) {
      const node = stack.shift()
      result.push({name: node.name})
      node.children?.forEach((v,i) => stack.splice(i,0,v))
    }
  })
  return result;
}

Answer 5

比较容易理解的 tree2List 的方法；

const tree2List = (arr) => {
    let ans = [], stack = [...arr];
    while (stack.length) {
        let t = stack.pop();
        ans.push({name: t.name});
        if( t.children && t.children.length) stack.push( ... t.children );
    }
    return ans;
}

console.log( tree2List(arr));

Answer 6

思路：

• 使用栈，每次需要处理一组节点，都先入栈，逐一处理。
• 出栈一个，处理一个（加入 result），再把其子节点压入栈（如果有）
• 由于栈是先进后出，但结果需要按原来的顺序，所以对一组数据进行压栈的时候，先反向

function flatTree(tree) {
    const stack = Array.isArray(tree) ? [...tree].reverse() : [tree];
    const result = [];
    while (stack.length) {
        const node = stack.pop();
        result.push(node);
        if (node.children?.length) {
            stack.push(...node.children.reverse());
        }
    }
    return result;
}

如果结构中需要把 children 给分离出去，while 中可以这样写（用解构来分离，参阅：JavaScript 数据处理 - 映射表篇 | 六、映射表的拆分）：

const { children, ...node } = stack.pop();
result.push(node);
if (children?.length) {
    stack.push(...children.reverse());
}

Answer 7

const arr = []; // 你的数组

const r = [];
const parent = [];

function getData(item) {
  console.log(item)
  if (item.name) {
    r.push({name: item.name});
  }
}

arr.forEach((cur) => {
  getData(cur);
  if (cur.children) {
    parent.push(cur)
  }
})

while(parent.length) {
  const cur = parent.shift();
  const children = cur.children;

  children.forEach(child => {
    getData(child)
    
    if (child.children) {
      parent.push(child)
    }
  });
  
  if (children.children) {
    parent.push(children.children)
  }
}


console.log(r);

当然此处没有考虑平铺的顺序

Answer 8

function transform(tree) {
    var ret = [];
    for (var stack = tree.slice(), top, obj; stack.length;) {
        top = stack.shift(), ret[ret.length] = obj = {};
        for (var key in top) {
            if (top[key] instanceof Array) {
                stack.unshift.apply(stack, top[key].slice());
            } else {
                obj[key] = top[key];
            }
        }
    }
    return ret;
}
console.dir(transform(arr));