下面的題目是我刷的Leetcode上關(guān)于深度優(yōu)先搜索的題目，因?yàn)轭}還沒刷完，所以這篇文章會(huì)將不時(shí)地進(jìn)行續(xù)更
package cn.infobuy.gouqi.demo;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* DFS 深度優(yōu)先搜索
* @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; }
}
/**
* 在每個(gè)樹行中找最大值
* @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) {
// 葉子節(jié)點(diǎn)
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;
}
/**
* 判斷是否為相同的樹
* 給定兩個(gè)二叉樹，編寫一個(gè)函數(shù)來檢驗(yàn)它們是否相同南片。如果兩個(gè)樹在結(jié)構(gòu)上相同变姨，并且節(jié)點(diǎn)具有相同的值纽匙，則認(rèn)為它們是相同的丽惭。
* 通過深度優(yōu)先遍歷
* @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;
}
/**
* 驗(yàn)證是否為二叉搜索樹 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;
}
/**
* 驗(yàn)證是否是平衡二叉樹
* 平衡二叉樹的特征：一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對值不超過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;
}
/**
* 路徑總和
* 給定一個(gè)二叉樹和一個(gè)目標(biāo)和击奶，判斷該樹中是否存在根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和
* @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
* 給定一個(gè)二叉樹和一個(gè)目標(biāo)和责掏，找到所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑總和等于給定目標(biāo)和的路徑
* @param root
* @param sum
* @return
*/
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root==null) {
return new ArrayList<List<Integer>>(0);
}
// 葉子節(jié)點(diǎn)
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);
}
}
// 子節(jié)點(diǎn)
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;
}
/**
* 返回二叉樹的所有路徑
* 給定一個(gè)二叉樹柜砾，返回所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。
* @param root
* @return
*/
public List<String> binaryTreePaths(TreeNode root) {
if(root==null) {
return new ArrayList<String>(0);
}
// 葉子節(jié)點(diǎn)
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;
}
/**
* 被圍繞的區(qū)域
* 給定一個(gè)二維的矩陣换衬，包含 'X' 和 'O'（字母 O）痰驱。找到所有被 'X' 圍繞的區(qū)域，并將這些區(qū)域里所有的 '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') {
//如果左上相連的區(qū)域包含'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;
}
}
// 避免重復(fù)入棧操作
if(board[x][y]=='-') {
return true;
}
// 表示這個(gè)節(jié)點(diǎn)第一次入棧操作
board[x][y]='-';
/**
* 不管有多少棧担映，一共加起來最多只有（n-x乘y) 個(gè)幀才對
*/
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;
}
/**
* 求島嶼的個(gè)數(shù)
* 給定一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，計(jì)算島嶼的數(shù)量叫潦。
* 一個(gè)島被水包圍另萤，并且它是通過水平方向或垂直方向上相鄰的陸地連接而成的。你可以假設(shè)網(wǎng)格的四個(gè)邊均被水包圍诅挑。
* @param grid
* @return
*/
public int numIslands(char[][] grid) {
int length = grid.length;
if(length==0) {
return 0;
}
int counter = 0;
/**
* 坐標(biāo)（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;
}
/**
* 清除附近的島嶼四敞，防止重復(fù)計(jì)算
* @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;
}
// 這里一個(gè)節(jié)點(diǎn)不會(huì)重復(fù)生成一個(gè)棧，
// 如果之前滿足條件能入棧的話拔妥，在入棧之后這個(gè)滿足條件就會(huì)改變忿危，之后就不會(huì)再重復(fù)入棧
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);
}
}
/**
* 低效做法：
* 有序鏈表轉(zhuǎn)換二叉搜索樹
* 1)把鏈表轉(zhuǎn)換成數(shù)組
* 2)遞歸插入數(shù)組的中間元素
* @param head
* @return
*/
public TreeNode sortedListToBST(ListNode head) {
if(head==null) {
return null;
}
// 將鏈表轉(zhuǎn)換為數(shù)組
List<Integer> list = new ArrayList<Integer>();
while(head!=null) {
list.add(head.val);
head=head.next;
}
// 遞歸在BST中插入數(shù)組元素
return halfInsertNode(list,0,list.size()-1);
}
/**
* 遞歸插入數(shù)組的中間元素
* @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;
}
/**
* 其實(shí)鏈表ListNode可以直接轉(zhuǎn)為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以兩倍的速度跑到末尾
// 此時(shí)slow所在的節(jié)點(diǎn)剛好位于中間
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) {
}
}
