深度优先搜索算法

（英语：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;
    }
}

快慢指针找到链表的中间结点，该结点为根结点 循环这个操作　　　

４.路径总和２　　

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

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;
        }


}