Leetcode上的dfs问题
2018-06-01 本文已影响0人
杭州痞老板
下面的题目是我刷的Leetcode上关于深度优先搜索的题目，因为题还没刷完，所以这篇文章会将不时地进行续更
package cn.infobuy.gouqi.demo;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* DFS 深度优先搜索
* @author Administrator
*
*/
public class DepthFirstSearchSolution {
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
/**
* 在每个树行中找最大值
* @param root
* @return
*/
public List<Integer> largestValues(TreeNode root) {
// Queue<TreeNode> queue = new LinkedList<TreeNode>();
// while(root!=null){
//
// }
return null;
}
public int sumNumbers(TreeNode root) {
if(root==null){
return 0;
}
return sumNumbers(root,0);
}
private int sumNumbers(TreeNode root,int prefixNumber) {
// 叶子节点
if(root.left==null&&root.right==null){
return prefixNumber*10+root.val;
}
int sumNumber=0;
if(root.left!=null){
sumNumber+=sumNumbers(root.left,prefixNumber*10+root.val);
}
if(root.right!=null){
sumNumber+=sumNumbers(root.right,prefixNumber*10+root.val);
}
return sumNumber;
}
/**
* 判断是否为相同的树
* 给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
* 通过深度优先遍历
* @param p
* @param q
* @return
*/
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null|q==null){
if(p==q){
return true;
}else{
return false;
}
}
return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
/**
* 判断是否为对称二叉树
* @param root
* @return
*/
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return isSymmetric(root.left,root.right);
}
private boolean isSymmetric(TreeNode left,TreeNode right){
if(left==null||right==null){
if(left==null&&right==null){
return true;
}else{
return false;
}
}
return (left.val==right.val)&&isSymmetric(left.left,right.right)&&isSymmetric(left.right,right.left);
}
/**
* 找出二叉树的深度
* @param root
* @return
*/
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
/**
* 验证是否为二叉搜索树 BST
* @param root
* @return
*/
public boolean isValidBST(TreeNode root) {
return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode root,long min,long max) {
if(root==null) {
return true;
}
return isValidBST(root.left,min,root.val)&&isValidBST(root.right,root.val,max)&&root.val>min&&root.val<max;
}
/**
* 验证是否是平衡二叉树
* 平衡二叉树的特征：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1
* @param root
* @return
*/
public boolean isBalanced(TreeNode root) {
if(root==null) {
return true;
}
return isBalanced(root.left)&&isBalanced(root.right)&&(Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1);
}
/**
* 找出二叉树的最小深度
* @param root
* @return
*/
public int minDepth(TreeNode root) {
if(root==null) {
return 0;
}
if(root.left==null&&root.right==null) {
return 1;
}
if(root.left==null) {
return minDepth(root.right)+1;
}
if(root.right==null) {
return minDepth(root.left)+1;
}
return Math.min(minDepth(root.left),minDepth(root.right))+1;
}
/**
* 路径总和
* 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和
* @param root
* @param sum
* @return
*/
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null) {
return false;
}
if(root.left==null&&root.right==null) {
return root.val==sum;
}
return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
}
/**
* 路径总和 II
* 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径
* @param root
* @param sum
* @return
*/
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root==null) {
return new ArrayList<List<Integer>>(0);
}
// 叶子节点
if(root.left==null&&root.right==null) {
if(sum==root.val) {
List<List<Integer>> iList = new ArrayList<List<Integer>>(0);
List<Integer> list = new LinkedList<Integer>();
list.add(root.val);
iList.add(list);
return iList;
}else {
return new ArrayList<List<Integer>>(0);
}
}
// 子节点
List<List<Integer>> mainList=new ArrayList<List<Integer>>(0);
if(root.left!=null){
List<List<Integer>> leftList = pathSum(root.left,sum-root.val);
if(leftList.size()>0) {
for(int i=0;i<leftList.size();i++) {
LinkedList<Integer> list = (LinkedList<Integer>) leftList.get(i);
list.addFirst(root.val);
}
mainList=leftList;
}
}
if(root.right!=null){
List<List<Integer>> rightList = pathSum(root.right,sum-root.val);
if(rightList.size()>0) {
for(int i=0;i<rightList.size();i++) {
LinkedList<Integer> list = (LinkedList<Integer>) rightList.get(i);
list.addFirst(root.val);
}
mainList.addAll(rightList);
}
}
return mainList;
}
/**
* 返回二叉树的所有路径
* 给定一个二叉树，返回所有从根节点到叶子节点的路径。
* @param root
* @return
*/
public List<String> binaryTreePaths(TreeNode root) {
if(root==null) {
return new ArrayList<String>(0);
}
// 叶子节点
if(root.left==null&&root.right==null) {
List<String> list = new ArrayList<String>(1);
list.add(root.val+"");
return list;
}
// 路径
List<String> paths = new ArrayList<String>();
if(root.left!=null) {
List<String> partPaths = binaryTreePaths(root.left);
for(int i = 0;i<partPaths.size();i++) {
paths.add(root.val+"->"+partPaths.get(i));
}
}
if(root.right!=null) {
List<String> partPaths = binaryTreePaths(root.right);
for(int i = 0;i<partPaths.size();i++) {
paths.add(root.val+"->"+partPaths.get(i));
}
}
return paths;
}
/**
* 被围绕的区域
* 给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
* @param board
*/
public void solve(char[][] board) {
int len = board.length;
if(len<=0) {
return;
}
for(int x=0;x<board.length;x++) {
for(int y=0;y<board[x].length;y++) {
if(board[x][y]=='O') {
//如果左上相连的区域包含'O'
boolean flag = edgeDonotHaveOBTWClear(board,x,y,x,y);
for(int i=0;i<board.length;i++) {
for(int j=0;j<board[i].length;j++) {
if(board[i][j]=='-') {
board[i][j]=flag?'X':'O';
}
}
}
}
}
}
}
/**
* 是否边界全部为'X' // 如果全部为'X' 则做下清理
* false 表示边界为'O'
* true 表示边界为'X'
* @param board
* @param x
* @param y
* @return
*/
private boolean edgeDonotHaveOBTWClear(char[][] board,int x,int y,int boundX,int boundY) {
if(x==0||y==0||x==board.length-1||y==board[0].length-1) {
if(board[x][y]=='X') {
return true;
}else {
return false;
}
}
// 碰壁返回
if(board[x][y]=='X') {
return true;
}
if(x<boundX&&y<boundY) {
if(board[x][y]=='X') {
return true;
}else {
return false;
}
}
// 避免重复入栈操作
if(board[x][y]=='-') {
return true;
}
// 表示这个节点第一次入栈操作
board[x][y]='-';
/**
* 不管有多少栈，一共加起来最多只有（n-x乘y) 个帧才对
*/
boolean reachEdgeDonotHaveO =
edgeDonotHaveOBTWClear(board,x+1,y,boundX,boundY)
&&edgeDonotHaveOBTWClear(board,x-1,y,boundX,boundY)
&&edgeDonotHaveOBTWClear(board,x,y-1,boundX,boundY)
&&edgeDonotHaveOBTWClear(board,x,y+1,boundX,boundY);
if(reachEdgeDonotHaveO) {
board[x][y]='X';
}
return reachEdgeDonotHaveO;
}
/**
* 求岛屿的个数
* 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。
* 一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
* @param grid
* @return
*/
public int numIslands(char[][] grid) {
int length = grid.length;
if(length==0) {
return 0;
}
int counter = 0;
/**
* 坐标（x,y）
*/
for(int x=0;x<length;x++) {
for(int y=0;y<grid[0].length;y++) {
if(grid[x][y]=='1') {
counter++;
clearNearByIslands(grid,x,y);
};
}
}
return counter;
}
/**
* 清除附近的岛屿，防止重复计算
* @param grid
* @param x
* @param y
*/
private void clearNearByIslands(char[][] grid,int x,int y) {
if(x<0||y<0||x>=grid.length||y>=grid[0].length) {
return;
}
// 这里一个节点不会重复生成一个栈，
// 如果之前满足条件能入栈的话，在入栈之后这个满足条件就会改变，之后就不会再重复入栈
if(grid[x][y]=='1') {
grid[x][y]='0';
clearNearByIslands(grid,x-1,y);
clearNearByIslands(grid,x+1,y);
clearNearByIslands(grid,x,y-1);
clearNearByIslands(grid,x,y+1);
}
}
/**
* 低效做法：
* 有序链表转换二叉搜索树
* 1)把链表转换成数组
* 2)递归插入数组的中间元素
* @param head
* @return
*/
public TreeNode sortedListToBST(ListNode head) {
if(head==null) {
return null;
}
// 将链表转换为数组
List<Integer> list = new ArrayList<Integer>();
while(head!=null) {
list.add(head.val);
head=head.next;
}
// 递归在BST中插入数组元素
return halfInsertNode(list,0,list.size()-1);
}
/**
* 递归插入数组的中间元素
* @param root
* @param list
* @param lgt
* @param rgt
*/
private TreeNode halfInsertNode(List<Integer> list,int lgt,int rgt) {
if(lgt>rgt) {
return null;
}
int mid = (lgt+rgt)/2;
TreeNode node = new TreeNode(list.get(mid));
node.left = halfInsertNode(list,lgt,mid-1);
node.right = halfInsertNode(list,mid+1,rgt);
return node;
}
public TreeNode sortedArrayToBST(int[] nums) {
if(nums==null) {
return null;
}
return halfInsertNode(nums,0,nums.length-1);
}
private TreeNode halfInsertNode(int[] list,int lgt,int rgt) {
if(lgt>rgt) {
return null;
}
int mid = (lgt+rgt)/2;
TreeNode node = new TreeNode(list[mid]);
node.left = halfInsertNode(list,lgt,mid-1);
node.right = halfInsertNode(list,mid+1,rgt);
return node;
}
/**
* 其实链表ListNode可以直接转为BST
* @param head
* @param end
* @return
*/
public TreeNode sortedList(ListNode head, ListNode end){
if (head == end){
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast != end && fast.next != end){
// fast以两倍的速度跑到末尾
// 此时slow所在的节点刚好位于中间
fast = fast.next.next;
slow = slow.next;
}
TreeNode root = new TreeNode(slow.val);
root.left = sortedList(head,slow);
root.right = sortedList(slow.next,end);
return root;
}
/**
* 二叉树展开为链表
* @param root
*/
public void flatten(TreeNode root) {
}
}
