二叉树遍历分为有两种，分别是广度优先遍历、深度优先遍历，而深度优先遍历又分成前序遍历、中序遍历和后序遍历。如下图。

    image.png

    当使用广度优先遍历时，顺序是：1-2-3-4-5-6-7。
    当使用深度优先遍历时，分三种情况（可以理解就是将父节点放在哪个位置进行遍历）：

    • 如果是前序遍历顺序是（父左右）：1-2-4-5-3-6-7；
    • 如果是中序遍历顺序是（左父右）：4-2-5-1-6-3-7；
    • 如果是后续遍历顺序是（左右父）：4-5-2-6-7-3-1；

    对于广度右边遍历，实现思路是通过创建一个队列，分别把所有节点都放到这个队列中，并且每次从队列中取出一个节点，直接队列中的节点被取完。（这里为了演示才使用打印语句，实际应用中可以去做一些其他的操作。）

    1. // 广度优先遍历
    3. function bfs(head) {
    4.     if (!head) return;
    6.     let list = [];                                // 创建队列，保存节点
    8.     list.push(head);
    10.     while (list.length > 0) {            // 只要队列不为空就依次循环
    11.         let node = list.shift();        // 取出队列第一个元素（即当前节点）进行处理，比如这里是打印
    12.         // console.log(node);
    14.     // 判断当前节点是否有子节点，有的话就加入到队列中
    15.         if (node.left) list.push(node.left);
    16.         if (node.right) list.push(node.right);
    17.     }
    18. }

    对于深度右边遍历就很简单，就是递归遍历所有节点，直到所有的节点都被遍历完成。（这里为了演示才使用打印语句，实际应用中可以去做一些其他的操作。）

    1. // 深度优先遍历
    3. // 前序遍历
    4. function preOrder(head) {
    5.     if (!head) return;
    7.     let node = head;
    8.     // console.log(node);
    9.     if (node.left) dfs(node.left);
    10.     if (node.right) dfs(node.right);
    11. }
    13. // 中序遍历
    14. function inOrder(head) {
    15.     if (!head) return;
    17.     let node = head;
    18.     if (node.left) dfs(node.left);
    19.     // console.log(node);
    20.     if (node.right) dfs(node.right);
    21. }
    23. // 后序遍历
    24. function postOrder(head) {
    25.     if (!head) return;
    27.     let node = head;
    28.     if (node.left) dfs(node.left);
    29.     if (node.right) dfs(node.right);
    30.     // console.log(node);
    31. }