线性迭代

对线性结构的遍历，如： 数组、链表

横向: 循环

// 线性迭代-横向
function traverse1(arr) {
    for (let i = 0; i < arr.length; i++) {
        console.log(arr[i]);
    }
}

纵向: 递归

const arr = [1,2,3,4,5].reverse();
traverse(arr);
// 线性迭代-纵向(递归)
function traverse(arr) {
    traverseCall(arr, 0);
    function traverseCall(arr, i) {
        if (i > arr.length) return;
        console.log(arr[i]);
        i++;
        traverseCall(arr, i);
    }
}

线性迭代-链表

横向：循环

interface Node {
    val: string;
  next: Node | null;
}
function traverse(head: Node) {
    // for循环
    for (let p=head;p!=null;p=p.next) {
        // 访问p.data
    }
    // or while
    let p = head;
    while(p!=null) {
        // 访问p.data
        p = p.next;
    }
}

纵向：递归

interface Node {
    val: string;
  next: Node | null;
}

function traverse(head: Node) {
    if (!head) return;
    traverse(head.next);
}

非线性迭代-树

DFS-递归版

二叉树

interface TreeNode {
    val: string;
  left: TreeNode | null;
  right: TreeNode | null;
}

# 二叉树
function traverse(root: TreeNode) {
    if (!root) return;
    traverse(root.left);
    traverse(root.right);
}

由DFS演化出的 前中后序遍历、

function traverse(root: TreeNode) {
    if (!root) return;
      // 前序遍历 console.log(root);
    traverse(root.left);
    // 中序遍历 console.log(root);
    traverse(root.right);
    // 后序遍历 console.log(root);
}

二叉树的递归遍历方式和链表的递归遍历方式，相似不？
再看看二叉树结构和单链表结构，相似不？如果再多几条叉，N 叉树会不会遍历？

# N叉树
interface TreeNode {
    val: string;
  children: TreeNode[] | null;
}

function traverse(root: TreeNode) {
    if (!root) return;
    // traverse(root.left);
    // traverse(root.right);
    for(let child of root.children) {
        traverse(child);
    } 
}

N 叉树的遍历又可以扩展为图的遍历，因为图就是好几 N 叉棵树的结合体。
图是可能出现环的？这个很好办，用个布尔数组 visited 做标记就行了

DFS-迭代版

将递归的代码，用栈存储即可转为迭代版

BFS

广度优先遍历，对应实例：层序遍历
思路是：从一个点开始，向四周开始扩散。每次将一个节点周围的所有节点加入队列

# 框架
function BFS(graph,start,end){
    let queue = [],visited = new Map();
    queue.add(start);
    visited.set(start,1);

    while(queue.length){
        # 1, 从一个点开始
        let node = queue.shift();
        visited.set(node,1);

        // 处理当前访问的节点
        process(node);
        # 2, 向四周开始扩散 找node的邻近节点
        // 1. 找node的邻近节点  2.在邻近节点筛选出没被访问过的
        nodes = generate_ralated_nodes(node);
                # 3. 将一个节点周围的所有节点加入队列
        queue.add(...nodes)// 象征性写法..
    }
}

function levelOrder(root){
    if(!root) return [];
    let result = [];
    let queue = [root];

    while(queue.length){
        let prevLevelLen = queue.length;
        let curRes = [];// 存放上层全部节点

        while(prevLevelLen--){
             # 1, 从一个点开始
            let node = queue.shift();
            curRes.push(node.val);
             # 2 node.left, node.right
             # 3 放入队列
              // 将 cur 的相邻节点加入队列
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        result.push(curRes);
    }

    return result;
}

线性迭代高级技巧：双指针

高级技巧：滑动窗口