LeetCode上Tag为深度优先搜索(Depth-frist Search)的题目整理

101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
分析:这道题既可以用深度优先搜索DFS,也可以用广度优先搜索BFS。深度优先搜索的思路为:
传入root的左子树和右子树。如果两个都为NULL,则是对称的。如果两边都不为NULL并且两边的所对应的val相等,那就判断root->left->left和root->left->right是否对称,且判断root->left->right和root->right->left是否对称。。。
其余情况下return false;

257. Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:

1
/ \
2 3
\
5
All root-to-leaf paths are:
[“1->2->5”, “1->3”]
分析:典型的深度优先搜索,dfs函数思路为:
dfs函数中参数传入一个string,该String将每次结点的值连接起来,直到递归出口的时候返回;
当该结点有左孩子的时候,将左孩子的值连接到字符串尾部;
当该结点有右孩子的时候,将右孩子的值连接到字符串尾部;
当该结点无左右孩子的时候,将字符串push入数组后return;

100. Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
分析:递归函数每次传入两棵树中的各一个结点。先传入两个树的root结点。若root结点均不为空,则判断这两个结点的值是否相等,和这两个结点的左孩子、右孩子是否相等~如果都满足则return true,否则return false~若传入的结点不是都不空的,判断是否同时都空~如果一个空一个不空那么是false~所以最后要加上一句return p == NULL && q == NULL;~~~~

104. Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
分析:分类讨论,设当前结点为root,如果root->left 和 root->right都为NULL,则返回1;
如果root->left不为NULL但是root->right为NULL,返回root->left为根节点的子树的最大层数+1;
如果root->right不为NULL但是root->left为NULL,返回root->right为根节点的子树的最大层数+1;
如果root->right和root->right都不为NULL,则返回以root->left为根节点的子树的层数和以root->right为根节点的子树的层数中的较大的那个值+1。

110. Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
分析:判断一棵二叉树是否为平衡二叉树~设当前结点为root,设两个变量l和r分别表示以root为根节点的子树的左边的高度和右边的高度。如果root结点没有左孩子,那么l = 0;否则l = dfs(root->left);如果root结点没有右孩子,那么r = 0;否则r = dfs(root->right);以root为根节点的子树的高度为它的左边的高度l和右边的高度r两个中较大的那一个+1;当root根节点为空的时候,说明它的父结点的高度为1。如果l和r的绝对值大于等于2则返回false(在这里将标志flag置为0)。

111. Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
分析:这道题即可以用深度优先,又可以用广度优先来做。这里用深度优先:
分析:分类讨论,设当前结点为root,如果root->left 和 root->right都为NULL,则返回1;
如果root->left不为NULL但是root->right为NULL,返回root->left为根节点的子树的最小层数+1;
如果root->right不为NULL但是root->left为NULL,返回root->right为根节点的子树的最小层数+1;
如果root->right和root->right都不为NULL,则返回以root->left为根节点的子树的层数和以root->right为根节点的子树的层数中的较小的那个值+1。

112. Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
分析:如果当前结点root没有左孩子left并且没有右孩子right,并且sum == root->val则return true;否则的话将root的左孩子left和sum-root->val的剩余需要的值传入函数作为参数进一步检验~如果当前root == NULL 则return false;说明没有达到该路径和为sum的要求。

还有几道深度优先:

POJ 1321-棋盘问题-简单搜索
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
Input 输入含有多组测试数据。
每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。
Output

对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。
Sample Input

2 1
#.
.#
4 4
…#
..#.
.#..
#…
-1 -1
Sample Output

2
1

POJ 1426-Find The Multiple-深度优先搜索dfs
Description
Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
Input
The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.
Output
For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.
Sample Input
2
6
19
0
Sample Output
10
100100100100100100
111111111111111111

POJ-2488 A Knights Journey-深度优先搜索
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?

Problem
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.
Input

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .
Output

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.
Sample Input

3
1 1
2 3
4 3
Sample Output
Scenario #1:
A1
Scenario #2:
impossible
Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
Source
TUD Programming Contest 2005, Darmstadt, Germany

4.1 深度优先搜索
全排列 123456789 数字,输出第n个

4.1深度优先搜索-xxx + xxx = xxx