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
  1. 反复上述操作，直至拜访完整棵树
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;};