深度优先搜索算法
(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。
简单说:就是一头扎到底的玩法。我们选择一条支路,尽可能不断地深入,如果遇到死路就往回退,回退过程中如果遇到没探索过的支路,就进入该支路继续深入
因发明「深度优先搜索算法」,约翰 · 霍普克洛夫特与罗伯特 · 塔扬在1986年共同获得计算机领域的最高奖:图灵奖。
嘻嘻 配一张与约翰 · 霍普克洛夫特爷爷的合照
1. 合并二叉树
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠,他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。 递归实现的Java代码
public class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if(t1==null)
return t2;
if(t2==null)
return t1;
t1.val+=t2.val;
t1.right=mergeTrees(t1.right,t2.right);
t1.left=mergeTrees(t1.left,t2.left);
return t1;
}
}
2.根据中序,后序遍历数组还原二叉树
public class Solution6 {
int inIndex;
int postIndex;
public TreeNode buildTree(int[] inorder, int[] postorder) {
inIndex=inorder.length-1;
postIndex=postorder.length-1;
return helper(inorder,postorder,(long)Integer.MAX_VALUE+1);
}
public TreeNode helper(int[] inorder, int[] postorder, long stop){
if(postIndex<0){
return null;
}
if(inorder[inIndex]==stop){
inIndex--;
return null;
}
int val=postorder[postIndex--];
TreeNode root=new TreeNode(val);
root.right=helper(inorder,postorder,val);
root.left=helper(inorder,postorder,stop);
return root;
}
}
根据后序遍历的特点,知最后为根结点,连续将后序遍历的后面元素按顺序依次转成树的右节点,
直到该结点的值等于中序遍历数组的最后一个元素才返回null,
根据中序 前序遍历数组还原二叉树
也是同理相反,连续将前序遍历数组按顺序写到树的左结点,直到该结点的值等于中序遍历数组的第一个元素才返回null
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length==0 || inorder.length==0) {
return null;
}
//根据前序数组的第一个元素,就可以确定根节点
TreeNode root = new TreeNode(preorder[0]);
for(int i=0;i<preorder.length;++i) {
//用preorder[0]去中序数组中查找对应的元素
if(preorder[0]==inorder[i]) {
//将前序数组分成左右两半,再将中序数组分成左右两半
//之后递归的处理前序数组的左边部分和中序数组的左边部分
//递归处理前序数组右边部分和中序数组右边部分
int[] pre_left = Arrays.copyOfRange(preorder,1,i+1);
int[] pre_right = Arrays.copyOfRange(preorder,i+1,preorder.length);
int[] in_left = Arrays.copyOfRange(inorder,0,i);
int[] in_right = Arrays.copyOfRange(inorder,i+1,inorder.length);
root.left = buildTree(pre_left,in_left);
root.right = buildTree(pre_right,in_right);
break;
}
}
return root;
}
}
3.有序链表转换为二叉搜索树
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
/**
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null) return null;
else if(head.next == null) return new TreeNode(head.val);
ListNode pre = head;
ListNode p = pre.next;
ListNode q = p.next;
//找到链表的中点p
while(q!=null && q.next!=null){
pre = pre.next;
p = pre.next;
q = q.next.next;
}
pre.next = null;//将中点左边的链表分开
TreeNode root = new TreeNode(p.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(p.next);
return root;
}
}
快慢指针找到链表的中间结点,该结点为根结点 循环这个操作
4.路径总和2
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
class Solution {
List<List<Integer>> list = new ArrayList<>();
ArrayList<Integer> inner = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if (root == null) return list;
sum -= root.val;
inner.add(root.val); // 入列表
if (root.left == null && root.right == null){
if (sum == 0){
list.add(new ArrayList<>(inner)); // 记得拷贝一份
}
}
if (root.left != null) pathSum(root.left, sum);
if (root.right != null) pathSum(root.right, sum);
inner.remove(inner.size()-1); //从列表中删除
return list;
}
}
岛屿最大面积
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为0。
public class Solution13 {
int X,Y;
// 用于向四周访问
int[] xarr = {1, -1, 0, 0};
int[] yarr = {0, 0, -1, 1};
public int maxAreaOfIsland(int[][] grid) {
// 获取X和Y
X = grid.length;
Y = grid[0].length;
int ans = 0;
// 遍历整个数组
for (int i = 0; i < X; i++) {
for (int j = 0; j < Y; j++) {
// 出现了陆地则进行深搜
if (grid[i][j] == 1) {
int sum = dfs(grid, i, j);
// 选出最大的面积
if (sum > ans) {
ans = sum;
}
}
}
}
return ans;
}
public int dfs(int[][] grid, int i, int j) {
int sum = 1; // 能进入该方法,岛屿面积默认为1
grid[i][j] = 0; // 访问了,则将该陆地变为海洋
// 向四周访问
for (int k = 0; k < 4; k++) {
int x = i + xarr[k];
int y = j + yarr[k];
if (x >= 0 && x < X && y >= 0 && y < Y && grid[x][y] == 1) {
sum += dfs(grid, x, y);
}
}
return sum;
}
}