广度优先、深度优先搜索算法——LeetCode

2021年11月21日 5点热度 0条评论

广度优先搜索(Breadth-first Search)

BFS在求解最短路径或者最短步数上有很多的应用。应用最多的是在走迷宫上。



分析

树的定义本身就是一种递归定义,因此对于树相关的算法题,递归是最好的解决思路(在递归深度允许的情况下)。

递归版

public class Solution {
    public boolean isSymmetric(TreeNode root) { 
        return root==null||isMirror(root.left,root.right);
    }
    private boolean isMirror(TreeNode p,TreeNode q){
        if(p==null&&q==null)
            return true;
        if(p==null||q==null)
            return false;
        if(p.val!=q.val)
            return false;
        return isMirror(p.left,q.right)&&isMirror(p.right,q.left);
    }
}

跌代版

public class Solution {
	public boolean isSymmetric(TreeNode root) {
	    if(root==null)  return true;
	    
	    Stack<TreeNode> stack = new Stack<TreeNode>();
	    TreeNode left, right;
	    if(root.left!=null){
	        if(root.right==null) return false;
	        stack.push(root.left);
	        stack.push(root.right);
	    }
	    else if(root.right!=null){
	        return false;
	    }
	        
	    while(!stack.empty()){
	        if(stack.size()%2!=0)   return false;
	        right = stack.pop();
	        left = stack.pop();
	        if(right.val!=left.val) return false;
	        
	        if(left.left!=null){//左子树的左子树和右子树的右子树比较
	            if(right.right==null)   return false;
	            stack.push(left.left);
	            stack.push(right.right);
	        }
	        else if(right.right!=null){
	            return false;
	        }
	            
	        if(left.right!=null){//左子树的右子树和右子树的左子树比较
	            if(right.left==null)   return false;
	            stack.push(left.right);
	            stack.push(right.left);
	        }
	        else if(right.left!=null){
	            return false;
	        }
	    } 
	    return true;
	}
}



分析

层次遍历可以利用队列实现。

public class Solution {
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> levels = new ArrayList<List<Integer>>();
		if (root == null)
			return levels;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		while (!queue.isEmpty()) {
			List<Integer> list = new ArrayList<Integer>();
			Queue<TreeNode> nextQueue = new LinkedList<TreeNode>();
			while (!queue.isEmpty()) {
				TreeNode node = queue.poll();
				list.add(node.val);//记录层次遍历的结果
				if (node.left != null)
					nextQueue.add(node.left);
				if (node.right != null)
					nextQueue.add(node.right);
			}
			queue = nextQueue;
			levels.add(list);
		}
		return levels;
	}
}



分析

与上一题的唯一区别:节点遍历的顺序会交替变换,我们只需要用一个变量标记每次遍历的顺序即可。

public class Solution {
	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> levels = new LinkedList<List<Integer>>();
		if (root == null)
			return levels;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		int mark = 0;//遍历方向的标记
		while (!queue.isEmpty()) {
			List<Integer> list = new ArrayList<Integer>();
			Queue<TreeNode> nextqueue = new LinkedList<TreeNode>();
			while (!queue.isEmpty()) {
				TreeNode node = queue.poll();
				list.add(node.val);
				if (node.left != null)
					nextqueue.add(node.left);
				if (node.right != null)
					nextqueue.add(node.right);
			}
			queue = nextqueue;
			if (mark == 1)//不同标记不同方向
				Collections.reverse(list);
			mark = (mark + 1) % 2;
			levels.add(list);
		}
		return levels;
	}
}


分析
与上上题的唯一区别:将结果集逆序。

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
    	List<List<Integer>> levels=new ArrayList<List<Integer>>(); 
    	if(root==null)return levels;
    	Queue<TreeNode> queue=new LinkedList<TreeNode>();
    	queue.add(root); 
    	while(!queue.isEmpty()){
    		List<Integer> list=new ArrayList<Integer>();
    		Queue<TreeNode> nextQueue=new LinkedList<TreeNode>();
    		while(!queue.isEmpty()){
    			TreeNode node=queue.poll();
    			list.add(node.val);
    			if(node.left!=null)nextQueue.add(node.left);
    			if(node.right!=null)nextQueue.add(node.right);
    		} 
    		queue=nextQueue;
    		levels.add(list);
    	}
    	Collections.reverse(levels);//将结果集逆序即可
    	return levels;
    }
}


递归版

public class Solution {
    public int minDepth(TreeNode root) {
        if(root==null)return 0;
        return doMinDepth(root);
    }
    public int doMinDepth(TreeNode root) {
    	if(root==null) return Integer.MAX_VALUE;
    	if(root.left==null&&root.right==null) return 1;
    	int leftDepth=doMinDepth(root.left);
    	int rightDepth=doMinDepth(root.right);
    	return 1+Math.min(leftDepth, rightDepth);
    }
}

迭代版

利用后序遍历可以遍历所有从根节点的路径。

public class Solution {
	public int minDepth(TreeNode root) {
		if (root == null)
			return 0;
		Stack<TreeNode> stack=new Stack<TreeNode>();
		 Map<TreeNode,Boolean> visit=new HashMap<TreeNode,Boolean>(); 
		int min=Integer.MAX_VALUE;
		TreeNode p=root;
		while(p!=null||!stack.isEmpty()){//后续遍历
			while(p!=null){
				stack.push(p);
				p=p.left;
			}
			p=stack.peek();
			if(p.left==null&&p.right==null){
				min=Math.min(min, stack.size());
			}
	        if(p.right!=null){//具有右子树  
	            if(visit.get(p)==null){//第一次出现在栈顶
	                visit.put(p, true);  
	                //处理右子树  
	                p=p.right;  
	            }  
	            else{//第二次出现在栈顶 
	                stack.pop();  
	                p=null;  //右子树已经处理过了
	            }  
	        }else{    
	            stack.pop();  
	            p=null;  
	        }  
		}
		return min;
	}
}



分析

初始化:location=0(<row=0,col=0>)。利用宽度优先遍历算法,搜寻从location(<row,col>)出发所有连通的'O’。然后判定连通集合是否被包围,如果被包围则全部置为‘X’,否则全部标记为未被包围。然后,从下一个可能被包围的location开始继续上述步骤,直到找不到下一个可能被包围的location,算法结束。

public class Solution {
	private void doSolve(char[][] board,HashSet<Integer> unSurrounded,int location){ 
		int m=board.length,n=board[0].length;
		while(location<m*n){//找到第一个可能被包围的'O'
			int r=location/n,c=location%n;
			if(board[r][c]=='O'&&!unSurrounded.contains(location)){
				break;
			}
			location++;
		}
		if(location==m*n)return;//处理完毕  
		//宽度优先遍历
		HashSet<Integer> founded=new HashSet<Integer>();//所有搜索到的
		HashSet<Integer> current=new HashSet<Integer>();//当前元素
		founded.add(location);
		current.add(location); 
		while(true){
			HashSet<Integer> newLocations=new HashSet<Integer>();
			for(Integer i:current){
				int r=i/n,c=i%n;
				//依次考虑上下左右的位置
				if(r>0&&board[r-1][c]=='O'&&!founded.contains(i-n)){
					founded.add(i-n);newLocations.add(i-n);}//上
				if(r<m-1&&board[r+1][c]=='O'&&!founded.contains(i+n)){
					founded.add(i+n);newLocations.add(i+n);}//下
				if(c>0&&board[r][c-1]=='O'&&!founded.contains(i-1)){
					founded.add(i-1);newLocations.add(i-1);}//左
				if(c<n-1&&board[r][c+1]=='O'&&!founded.contains(i+1)){
					founded.add(i+1);newLocations.add(i+1);}//右
			}
			if(newLocations.size()==0){
				break;
			}else{
				current=newLocations;//只有新增的位置,才能搜索到新增位置
			}
		}
		//检查是否被包含
		boolean surrounded=true; 
		for(Integer i:founded){ 
			int r=i/n,c=i%n;
			if(r==0||r==m-1||c==0||c==n-1){
				surrounded=false;
				break;
			}  
		}
		if(surrounded){
			for(Integer i:founded){
				int r=i/n,c=i%n;
				board[r][c]='X';
			}
		}else{
			for(Integer i:founded){
				unSurrounded.add(i);
			}
		}
		doSolve(board,unSurrounded,location);//递归求解 
	}
	public void solve(char[][] board) {
		if(board.length==0||board[0].length==0)return;
		HashSet<Integer> unSurrounded=new HashSet<Integer>();//未被包围的'O'
		doSolve(board,unSurrounded,0);
	}
}



分析

该问题等价于层次遍历过程中,每一层的末尾元素。

public class Solution {
	public List<Integer> rightSideView(TreeNode root) {
		List<Integer> res = new ArrayList<Integer>();
		if (root == null)
			return res;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		while (!queue.isEmpty()) {
			Queue<TreeNode> nextQueue = new LinkedList<TreeNode>();
			TreeNode last=null;//记录每层末尾的元素
			while (!queue.isEmpty()) {
				TreeNode node = queue.poll(); 
				last=node;
				if (node.left != null)
					nextQueue.add(node.left);
				if (node.right != null)
					nextQueue.add(node.right);
			}
			queue = nextQueue; 
			res.add(last.val);
		}
		return res;
	}
}



分析

依然是宽度优先遍历,思路几乎与上上题一致。从location开始搜索连通集合,然后将连通集合标记为已找到的island。然后,寻找下一个可能是island的location,继续上述搜索过程,直到找不到可能的island。

	private int findIslands(char[][] grid,HashSet<Integer> islandLocation,int location){
		int m=grid.length,n=grid[0].length;
		while(location<m*n){//找到第一个可能是island的'1'
			int r=location/n,c=location%n;
			if(grid[r][c]=='1'&&!islandLocation.contains(location)){
				break;
			}
			location++;
		}
		if(location==m*n) return 0;//处理完毕  
		//宽度优先遍历
		HashSet<Integer> founded=new HashSet<Integer>();//所有搜索到的'1'
		HashSet<Integer> current=new HashSet<Integer>();//当前元素
		founded.add(location);
		current.add(location); 
		while(true){
			HashSet<Integer> newLocations=new HashSet<Integer>();
			for(Integer i:current){
				int r=i/n,c=i%n;
				//依次考虑上下左右的位置
				if(r>0&&grid[r-1][c]=='1'&&!founded.contains(i-n)){
					founded.add(i-n);newLocations.add(i-n);}//上
				if(r<m-1&&grid[r+1][c]=='1'&&!founded.contains(i+n)){
					founded.add(i+n);newLocations.add(i+n);}//下
				if(c>0&&grid[r][c-1]=='1'&&!founded.contains(i-1)){
					founded.add(i-1);newLocations.add(i-1);}//左
				if(c<n-1&&grid[r][c+1]=='1'&&!founded.contains(i+1)){
					founded.add(i+1);newLocations.add(i+1);}//右
			}
			if(newLocations.size()==0){
				break;
			}else{
				current=newLocations;//只有新增的位置,才能搜索到新增位置
			}
		}
		for(Integer i:founded){//标记为island 
			islandLocation.add(i);
		} 
		return 1+findIslands(grid,islandLocation,location);//递归求解 
	}
    public int numIslands(char[][] grid) {
    	if(grid.length==0||grid[0].length==0)return 0;
    	HashSet<Integer> islandLocation=new HashSet<Integer>();
		return findIslands(grid,islandLocation,0);
    }

深度优先搜索(Depth-first Search)

在我们遇到的一些问题当中,有些问题我们不能够确切的找出数学模型,即找不出一种直接求解的方法,解决这一类问题,我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探,按照一定的顺序、规则,不断去试探,直到找到问题的解,试完了也没有找到解,那就是无解,试探时一定要试探完所有的情况(实际上就是穷举);

深度优先搜索(回溯法)作为最基本的搜索算法,其采用了一种“一直向下走,走不通就掉头”的思想(体会“回溯”二字),相当于采用了先根遍历的方法来构造搜索树。


分析

方案一:中序遍历

因为二叉查找数的中序遍历是递增的,我们可以利用这个性质进行验证。

public class Solution {
    public boolean isValidBST(TreeNode root) {
    	//查找树的中序遍历为递增的
    	if(root==null)return true;  
    	TreeNode pre=null;//上一个节点
		Stack<TreeNode> stack=new Stack<TreeNode>();
		TreeNode p=root;
		while(p!=null||!stack.isEmpty()){
			while(p!=null){ 
				stack.push(p);
				p=p.left;
			}
			p=stack.pop();
			if(pre==null||pre.val<p.val){
				pre=p;
			}else{
				return false;
			} 
			if(p.right!=null){//处理右子树
				p=p.right;
			}else{//处理上一层
				p=null;
			} 
		} 
		return true;
    }
}

方案二:深度优先搜索

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);//验证树中节点的值域
    }
    
    public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;//检查根节点的值是否在值域内
        //根据根节点的值,限定子树节点的值域
        return isValidBST(root.left, minVal, root.val) 
        		&& isValidBST(root.right, root.val, maxVal);
    }
}

分析

方案一:中序遍历

假如,正常的中序遍历结果为1,2,3,4,5,6,7,8。交换后的中序遍历结果变成1,7,3,4,5,6,2,8,我们如何找到两个颠倒位置的元素呢?
不难发现,重前往后第一个波峰,和从后往前第一个

标签: 暂无
最后更新:2021年11月21日