DFS（Deep First Search）深度优先搜寻 与 BFS（Breath First Search）广度优先搜寻

DFS：用到了栈构造，先进后出，重点在于递归，适合寻找特定指标

BFS：用到了队列构造，先进先出，重点在于队列，适合大范畴搜查

二叉树的深度优先

二叉树的前序遍历

二叉树的中序遍历

二叉树的后序遍历

（上面解法以中序遍历为例）

1. 递归

工夫复杂度：O(n)
空间复杂度：O(n)

先判断根节点是否存在，再遍历左节点，最初遍历右节点

var inorderTraversal = function(root) {const res = [];
    const inorder = (root) => {if (!root) {return;}
        inorder(root.left);
        res.push(root.val);
        inorder(root.right);
    }
    inorder(root);
    return res;
};

2. 迭代

工夫复杂度：O(n)
空间复杂度：O(n)
与办法 1 相似，区别在于递归时隐式保护一个栈，而在迭代时须要显式地将这个栈模仿进去，其余的实现与细节都雷同

var inorderTraversal = function(root) {const res = [];
    const stk = [];
    while (root || stk.length) {while (root) {stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
};

3. Morris 遍历

工夫复杂度：O(n)
空间复杂度：O(1)

1. 如果没有左节点，先将值退出答案数组，再拜访右节点，即 x = x.right
2. 如果有左节点，则找到左节点上最右的节点（即左子树中序遍历的最初一个节点，在中序遍历中的前驱节点），记为 predecessor。依据 predecessor 的右节点是否为空，进行如下操作：

• 如果 \textit{predecessor}predecessor 的右节点为空，则将其右节点指向 x，而后拜访左节点，即 x = x.left
• 如果 predecessor 的右节点不为空，则此时其右节点指向 x，阐明曾经遍历完左子树，咱们将 predecessor 的右节点置空，将 x 的值退出答案数组，而后拜访 x 的右节点，即 x = x.right

3. 反复上述操作，直至拜访完整棵树

var inorderTraversal = function(root) {const res = [];
    let predecessor = null;

    while (root) {if (root.left) {
            // predecessor 节点就是以后 root 节点向左走一步，而后始终向右走至无奈走为止
            predecessor = root.left;
            while (predecessor.right && predecessor.right !== root) {predecessor = predecessor.right;}

            // 让 predecessor 的右指针指向 root，持续遍历左子树
            if (!predecessor.right) {
                predecessor.right = root;
                root = root.left;
            }
            // 阐明左子树曾经拜访完了，咱们须要断开链接
            else {res.push(root.val);
                predecessor.right = null;
                root = root.right;
            }
        }
        // 如果没有左孩子，则间接拜访右孩子
        else {res.push(root.val);
            root = root.right;
        }
    }

    return res;
};

二叉树的广度遍历

二叉树的层序遍历

工夫复杂度：O(n)
空间复杂度：O(n)

var levelOrder = function(root) {const ret = [];
    if (!root) {return ret;}

    const q = [];
    q.push(root);
    while (q.length !== 0) {
        const currentLevelSize = q.length;
        ret.push([]);
        for (let i = 1; i <= currentLevelSize; ++i) {const node = q.shift();
            ret[ret.length - 1].push(node.val);
            if (node.left) q.push(node.left);
            if (node.right) q.push(node.right);
        }
    }
        
    return ret;
};