DFS(深度优先搜索)&BFS(广度优先搜索)

深度优先搜索

基本原理就是不断对子节点进行深度优先搜索，递归思想：

function dfs(root) {
  console.log(root.val);
  root.children.forEach(dfs);
}

广度优先搜索

借助队列数据结构，现将根结点入队，然后出队，访问节点并入队所有子节点。然后重复入队这些子节点，知道队列为空

function bfs(root) {
  let p = [root];
  while(p.length) {
    const t = p.shift();
    console.log(t.val)
    // 将当前节点的所有子节点入队，保证下一层的子节点顺序
    t.children.forEach(m => p.push(m))
  }
}

https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

https://stackoverflow.com/questions/5278580/non-recursive-depth-first-search-algorithm

例如，树结构是这样的：

var tree = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
      left: null,
      right: null
    },
    right: {
      val: 5,
      left: null,
      right: null
    }
  },
  right: {
    val: 3,
    left: null,
    right: null
  }
}

DFS输出：

https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/?ref=rp

https://www.techiedelight.com/postorder-tree-traversal-iterative-recursive/