概念

在此输入正文
如上图所示，对于每次搜索而言尽可能往深度前进，直到结点v的所有出发边都被找到然后回溯。通常用递归实现，遍历结果依赖每次选择遍历子结点的顺序。

LeetCode之深度优先搜索

332.Reconstruct Itinerary
重建飞行旅程，给定n段起点终点旅程，输出飞行目的地的先后顺序，从”JFK”为最初起点，可以返回飞行，若有多个答案，输出字典小序的那个。
Input: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]
Output: [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”]

  1. 由于一开始没有理解可以返回飞这一点，错误的认为这是一道拓扑排序题目
  2. 后来发现对于有向图中的环也要遍历到每一条边后，可以用DFS来遍历，每次遍历完一个节点后在路径前部推入新的地点
  3. 由于需要考虑到单词顺序，在建图的时候，邻接表中用优先队列(最小堆)来存储邻接节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var PriorityQueue = require('./PriorityQueue');
var findItinerary = function (tickets) {
  var res = [], neighbors = {};
  for (var i = 0; i < tickets.length; i++) {
    if (neighbors[tickets[i][0]] == undefined) {
      neighbors[tickets[i][0]] = new PriorityQueue(function comparator(s1, s2) {
        return s1 > s2;
      });
    }
    neighbors[tickets[i][0]].push(tickets[i][1]);
  }
  var start = 'JFK';
  DFS(neighbors, res, start);
  return res;
};

var DFS = function (neighbors, res, start) {
  while (neighbors[start] !== undefined && neighbors[start].size() > 0) {
    var newStart = neighbors[start].pop();
    DFS(neighbors, res, newStart);

  }
  res.unshift(start);
};

366.Find Leaves of Binary Tree
将二叉树中的叶子节点一层层构建出数组(每当去掉一层叶子后出现新的叶子)进行输出。

Input: 
 
     1
    / \
   2   3
  / \
 4   5
OutPut: [[4, 5, 3], [2], [1]]

这道题目的关键在于每次要找到叶子节点，也就是说需要深度优先遍历到叶子，然后用记录当前高度来对应数组的存储位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var BinaryTree = require('./BinaryTree');
var findLeaves = function (root) {
  var res = [];
  maxHeight(root, res);
  return res;
};

function maxHeight(root, res) {
  if (root === null) return 0;
  var height = Math.max(maxHeight(root.left, res), maxHeight(root.right, res)) + 1;
  if (res.length < height) {
    res.push([]);
  }
  res[height - 1].push(root.val);
  return height;
}

490.The Maze
给定二维迷宫、起点和终点，0表示空格，1表示墙，即障碍物，四周也是墙。球从起点出发后，可上下左右移动，每次都要沿一个方向撞墙为止。判断是否可到达指定终点。

Input 1: 
 0 0 1 0 0
 0 0 0 0 0
 0 0 0 1 0
 1 1 0 1 1
 0 0 0 0 0
 Input 2: 起点 = (0, 4)
 Input 3: 终点 = (4, 4)
 Output: True

二维移动是典型的无向图，对于每点而言，一般存在4个邻接点；对于判断能否到达终点，用BFS或DFS遍历即可，若遍历完整个图，还没有到达终点位置则不可到达终点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var canReachDest = function (maze, start, destination) {
  if (maze.length == 0 || maze[0].length == 0) return false;
  if (start[0] == destination[0] && start[1] == destination[1]) return true;
  var visited = [];
  for (var i = 0; i < maze.length; i++) {
    visited.push(new Array(maze[0].length).fill(false));
  }
  return DFS(maze, visited, start[0], start[1], destination);

};

function DFS(maze, visited, i, j, dest) {
  if (visited[i][j]) return false;
  if (i == dest[0] && j == dest[1]) return true;
  visited[i][j] = true;
  var dir = [[0, -1], [1, 0], [0, 1], [-1, 0]];
  for (var k = 0; k < dir.length; k++) {
    var newI = i, newJ = j;
    while (newI + dir[k][0] > -1 && newI + dir[k][0] < maze.length && newJ + dir[k][1] > -1 &&
    newJ + dir[k][1] < maze[0].length && maze[newI + dir[k][0]][newJ + dir[k][1]] != 1) {
      newI += dir[k][0];
      newJ += dir[k][1];
    }
    if (DFS(maze, visited, newI, newJ, dest)) return true;

  }
  return false;
}