鸣谢

本文还参考了如下优秀文章：

• 深度优先搜索与广度优先搜索的本质区别！

文章开篇对象相关作者表示真挚的感谢与敬意，如有侵权，请联系删除相关内容。

DFS

DFS 的英文全称 Depth First Search，即深度优先搜索。

深度优先搜索的核心思想是试图穷举所有的完整路径。

深度优先搜索的本质是栈结构。

我们来看下二叉树的先序遍历：

二叉树的先序遍历就是深度优先搜索思想的递归实现

/* 
需求：实现二叉树的先序遍历
思路：
   1
  /\
  2 3
传入一个节点，输出这个节点的 value
*/
function preorder(root) {
  if (!root) return;
  preorder(root.left);
  preorder(root.right);
}

DFS 练习

二叉树的最近公共祖先-236

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”



示例 1：


输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：


输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1


提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

将有序数组转换为二叉搜索树

删除二叉搜索树中的节点-450

路径总和 III-437

求根到叶子节点数字之和-129

二叉树的所有路径-257

左叶子之和-404

路径总和-112

平衡二叉树-110

对称二叉树-101

二叉树的最小深度-111

二叉树的最大深度-104

二叉树的层序遍历-102

路径总和 II-113

相同的树-100

BFS

BFS 的英文全称是 Breadth First Search ，即广度优先原则。广度优先以 “广度” 为第一要务，一层层扫描，如下图：

丢弃已访问的坐标、记录新观察到的坐标，这个顺序符合先进先出的原则，所以 BFS 的实现和队列有着很密切的关系。

还以二叉树为例，我们看下二叉树的层序遍历，如下图：

代码实现：

function BFS(root) {
  const queue = [];
  queue.push(root);
  while (queue.length) {
    const top = queue[0];
    console.log(top.val);
    if (top.left) {
      queue.push(top.left);
    }
    if (top.right) {
      queue.push(top.right);
    }
    queue.unshift();
  }
}

BFS(root);

/* 
A
B
C
D
E
F
*/

BFS 练习

面试题32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。



例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回：

[3,9,20,15,7]


提示：

节点总数 <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

    const queue = [];
    const res = [];
    queue.push(root);

    while (queue.length) {
        const top = queue[0];
        res.push(top.val);
        if (top.left) {
            queue.push(top.left);
        }
        if (top.right) {
            queue.push(top.right);
        }
        queue.shift();
    }
    return res;
};

跳跃游戏 IV-1345

跳跃游戏 III-1306

二叉树的最小深度-111

二叉树的最大深度-104

二叉树的右视图-199

二叉树的层序遍历-102

相同的树-100