devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：小丑西瓜9 | 2024-04-25 08:45:53

赞

踩

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

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

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



分析

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

递归版

  1. public class Solution {
  2.     public boolean isSymmetric(TreeNode root) { 
  3.         return root==null||isMirror(root.left,root.right);
  4.     }
  5.     private boolean isMirror(TreeNode p,TreeNode q){
  6.         if(p==null&&q==null)
  7.             return true;
  8.         if(p==null||q==null)
  9.             return false;
  10.         if(p.val!=q.val)
  11.             return false;
  12.         return isMirror(p.left,q.right)&&isMirror(p.right,q.left);
  13.     }
  14. }
跌代版 

  1. public class Solution {
  2. 	public boolean isSymmetric(TreeNode root) {
  3. 	    if(root==null)  return true;
  4. 	    
  5. 	    Stack<TreeNode> stack = new Stack<TreeNode>();
  6. 	    TreeNode left, right;
  7. 	    if(root.left!=null){
  8. 	        if(root.right==null) return false;
  9. 	        stack.push(root.left);
  10. 	        stack.push(root.right);
  11. 	    }
  12. 	    else if(root.right!=null){
  13. 	        return false;
  14. 	    }
  15. 	        
  16. 	    while(!stack.empty()){
  17. 	        if(stack.size()%2!=0)   return false;
  18. 	        right = stack.pop();
  19. 	        left = stack.pop();
  20. 	        if(right.val!=left.val) return false;
  21. 	        
  22. 	        if(left.left!=null){//左子树的左子树和右子树的右子树比较
  23. 	            if(right.right==null)   return false;
  24. 	            stack.push(left.left);
  25. 	            stack.push(right.right);
  26. 	        }
  27. 	        else if(right.right!=null){
  28. 	            return false;
  29. 	        }
  30. 	            
  31. 	        if(left.right!=null){//左子树的右子树和右子树的左子树比较
  32. 	            if(right.left==null)   return false;
  33. 	            stack.push(left.right);
  34. 	            stack.push(right.left);
  35. 	        }
  36. 	        else if(right.left!=null){
  37. 	            return false;
  38. 	        }
  39. 	    } 
  40. 	    return true;
  41. 	}
  42. }



分析

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

  1. public class Solution {
  2. 	public List<List<Integer>> levelOrder(TreeNode root) {
  3. 		List<List<Integer>> levels = new ArrayList<List<Integer>>();
  4. 		if (root == null)
  5. 			return levels;
  6. 		Queue<TreeNode> queue = new LinkedList<TreeNode>();
  7. 		queue.add(root);
  8. 		while (!queue.isEmpty()) {
  9. 			List<Integer> list = new ArrayList<Integer>();
  10. 			Queue<TreeNode> nextQueue = new LinkedList<TreeNode>();
  11. 			while (!queue.isEmpty()) {
  12. 				TreeNode node = queue.poll();
  13. 				list.add(node.val);//记录层次遍历的结果
  14. 				if (node.left != null)
  15. 					nextQueue.add(node.left);
  16. 				if (node.right != null)
  17. 					nextQueue.add(node.right);
  18. 			}
  19. 			queue = nextQueue;
  20. 			levels.add(list);
  21. 		}
  22. 		return levels;
  23. 	}
  24. }



分析

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

  1. public class Solution {
  2. 	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  3. 		List<List<Integer>> levels = new LinkedList<List<Integer>>();
  4. 		if (root == null)
  5. 			return levels;
  6. 		Queue<TreeNode> queue = new LinkedList<TreeNode>();
  7. 		queue.add(root);
  8. 		int mark = 0;//遍历方向的标记
  9. 		while (!queue.isEmpty()) {
  10. 			List<Integer> list = new ArrayList<Integer>();
  11. 			Queue<TreeNode> nextqueue = new LinkedList<TreeNode>();
  12. 			while (!queue.isEmpty()) {
  13. 				TreeNode node = queue.poll();
  14. 				list.add(node.val);
  15. 				if (node.left != null)
  16. 					nextqueue.add(node.left);
  17. 				if (node.right != null)
  18. 					nextqueue.add(node.right);
  19. 			}
  20. 			queue = nextqueue;
  21. 			if (mark == 1)//不同标记不同方向
  22. 				Collections.reverse(list);
  23. 			mark = (mark + 1) % 2;
  24. 			levels.add(list);
  25. 		}
  26. 		return levels;
  27. 	}
  28. }


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

  1. public class Solution {
  2.     public List<List<Integer>> levelOrderBottom(TreeNode root) {
  3.     	List<List<Integer>> levels=new ArrayList<List<Integer>>(); 
  4.     	if(root==null)return levels;
  5.     	Queue<TreeNode> queue=new LinkedList<TreeNode>();
  6.     	queue.add(root); 
  7.     	while(!queue.isEmpty()){
  8.     		List<Integer> list=new ArrayList<Integer>();
  9.     		Queue<TreeNode> nextQueue=new LinkedList<TreeNode>();
  10.     		while(!queue.isEmpty()){
  11.     			TreeNode node=queue.poll();
  12.     			list.add(node.val);
  13.     			if(node.left!=null)nextQueue.add(node.left);
  14.     			if(node.right!=null)nextQueue.add(node.right);
  15.     		} 
  16.     		queue=nextQueue;
  17.     		levels.add(list);
  18.     	}
  19.     	Collections.reverse(levels);//将结果集逆序即可
  20.     	return levels;
  21.     }
  22. }


递归版

  1. public class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if(root==null)return 0;
  4.         return doMinDepth(root);
  5.     }
  6.     public int doMinDepth(TreeNode root) {
  7.     	if(root==null) return Integer.MAX_VALUE;
  8.     	if(root.left==null&&root.right==null) return 1;
  9.     	int leftDepth=doMinDepth(root.left);
  10.     	int rightDepth=doMinDepth(root.right);
  11.     	return 1+Math.min(leftDepth, rightDepth);
  12.     }
  13. }
迭代版

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

  1. public class Solution {
  2. 	public int minDepth(TreeNode root) {
  3. 		if (root == null)
  4. 			return 0;
  5. 		Stack<TreeNode> stack=new Stack<TreeNode>();
  6. 		 Map<TreeNode,Boolean> visit=new HashMap<TreeNode,Boolean>(); 
  7. 		int min=Integer.MAX_VALUE;
  8. 		TreeNode p=root;
  9. 		while(p!=null||!stack.isEmpty()){//后续遍历
  10. 			while(p!=null){
  11. 				stack.push(p);
  12. 				p=p.left;
  13. 			}
  14. 			p=stack.peek();
  15. 			if(p.left==null&&p.right==null){
  16. 				min=Math.min(min, stack.size());
  17. 			}
  18. 	        if(p.right!=null){//具有右子树  
  19. 	            if(visit.get(p)==null){//第一次出现在栈顶
  20. 	                visit.put(p, true);  
  21. 	                //处理右子树  
  22. 	                p=p.right;  
  23. 	            }  
  24. 	            else{//第二次出现在栈顶 
  25. 	                stack.pop();  
  26. 	                p=null;  //右子树已经处理过了
  27. 	            }  
  28. 	        }else{    
  29. 	            stack.pop();  
  30. 	            p=null;  
  31. 	        }  
  32. 		}
  33. 		return min;
  34. 	}
  35. }


分析

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

  1. public class Solution {
  2. 	private void doSolve(char[][] board,HashSet<Integer> unSurrounded,int location){ 
  3. 		int m=board.length,n=board[0].length;
  4. 		while(location<m*n){//找到第一个可能被包围的'O'
  5. 			int r=location/n,c=location%n;
  6. 			if(board[r][c]=='O'&&!unSurrounded.contains(location)){
  7. 				break;
  8. 			}
  9. 			location++;
  10. 		}
  11. 		if(location==m*n)return;//处理完毕  
  12. 		//宽度优先遍历
  13. 		HashSet<Integer> founded=new HashSet<Integer>();//所有搜索到的
  14. 		HashSet<Integer> current=new HashSet<Integer>();//当前元素
  15. 		founded.add(location);
  16. 		current.add(location); 
  17. 		while(true){
  18. 			HashSet<Integer> newLocations=new HashSet<Integer>();
  19. 			for(Integer i:current){
  20. 				int r=i/n,c=i%n;
  21. 				//依次考虑上下左右的位置
  22. 				if(r>0&&board[r-1][c]=='O'&&!founded.contains(i-n)){
  23. 					founded.add(i-n);newLocations.add(i-n);}//上
  24. 				if(r<m-1&&board[r+1][c]=='O'&&!founded.contains(i+n)){
  25. 					founded.add(i+n);newLocations.add(i+n);}//下
  26. 				if(c>0&&board[r][c-1]=='O'&&!founded.contains(i-1)){
  27. 					founded.add(i-1);newLocations.add(i-1);}//左
  28. 				if(c<n-1&&board[r][c+1]=='O'&&!founded.contains(i+1)){
  29. 					founded.add(i+1);newLocations.add(i+1);}//右
  30. 			}
  31. 			if(newLocations.size()==0){
  32. 				break;
  33. 			}else{
  34. 				current=newLocations;//只有新增的位置，才能搜索到新增位置
  35. 			}
  36. 		}
  37. 		//检查是否被包含
  38. 		boolean surrounded=true; 
  39. 		for(Integer i:founded){ 
  40. 			int r=i/n,c=i%n;
  41. 			if(r==0||r==m-1||c==0||c==n-1){
  42. 				surrounded=false;
  43. 				break;
  44. 			}  
  45. 		}
  46. 		if(surrounded){
  47. 			for(Integer i:founded){
  48. 				int r=i/n,c=i%n;
  49. 				board[r][c]='X';
  50. 			}
  51. 		}else{
  52. 			for(Integer i:founded){
  53. 				unSurrounded.add(i);
  54. 			}
  55. 		}
  56. 		doSolve(board,unSurrounded,location);//递归求解 
  57. 	}
  58. 	public void solve(char[][] board) {
  59. 		if(board.length==0||board[0].length==0)return;
  60. 		HashSet<Integer> unSurrounded=new HashSet<Integer>();//未被包围的'O'
  61. 		doSolve(board,unSurrounded,0);
  62. 	}
  63. }


分析

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

  1. public class Solution {
  2. 	public List<Integer> rightSideView(TreeNode root) {
  3. 		List<Integer> res = new ArrayList<Integer>();
  4. 		if (root == null)
  5. 			return res;
  6. 		Queue<TreeNode> queue = new LinkedList<TreeNode>();
  7. 		queue.add(root);
  8. 		while (!queue.isEmpty()) {
  9. 			Queue<TreeNode> nextQueue = new LinkedList<TreeNode>();
  10. 			TreeNode last=null;//记录每层末尾的元素
  11. 			while (!queue.isEmpty()) {
  12. 				TreeNode node = queue.poll(); 
  13. 				last=node;
  14. 				if (node.left != null)
  15. 					nextQueue.add(node.left);
  16. 				if (node.right != null)
  17. 					nextQueue.add(node.right);
  18. 			}
  19. 			queue = nextQueue; 
  20. 			res.add(last.val);
  21. 		}
  22. 		return res;
  23. 	}
  24. }


分析

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

  1. 	private int findIslands(char[][] grid,HashSet<Integer> islandLocation,int location){
  2. 		int m=grid.length,n=grid[0].length;
  3. 		while(location<m*n){//找到第一个可能是island的'1'
  4. 			int r=location/n,c=location%n;
  5. 			if(grid[r][c]=='1'&&!islandLocation.contains(location)){
  6. 				break;
  7. 			}
  8. 			location++;
  9. 		}
  10. 		if(location==m*n) return 0;//处理完毕  
  11. 		//宽度优先遍历
  12. 		HashSet<Integer> founded=new HashSet<Integer>();//所有搜索到的'1'
  13. 		HashSet<Integer> current=new HashSet<Integer>();//当前元素
  14. 		founded.add(location);
  15. 		current.add(location); 
  16. 		while(true){
  17. 			HashSet<Integer> newLocations=new HashSet<Integer>();
  18. 			for(Integer i:current){
  19. 				int r=i/n,c=i%n;
  20. 				//依次考虑上下左右的位置
  21. 				if(r>0&&grid[r-1][c]=='1'&&!founded.contains(i-n)){
  22. 					founded.add(i-n);newLocations.add(i-n);}//上
  23. 				if(r<m-1&&grid[r+1][c]=='1'&&!founded.contains(i+n)){
  24. 					founded.add(i+n);newLocations.add(i+n);}//下
  25. 				if(c>0&&grid[r][c-1]=='1'&&!founded.contains(i-1)){
  26. 					founded.add(i-1);newLocations.add(i-1);}//左
  27. 				if(c<n-1&&grid[r][c+1]=='1'&&!founded.contains(i+1)){
  28. 					founded.add(i+1);newLocations.add(i+1);}//右
  29. 			}
  30. 			if(newLocations.size()==0){
  31. 				break;
  32. 			}else{
  33. 				current=newLocations;//只有新增的位置，才能搜索到新增位置
  34. 			}
  35. 		}
  36. 		for(Integer i:founded){//标记为island 
  37. 			islandLocation.add(i);
  38. 		} 
  39. 		return 1+findIslands(grid,islandLocation,location);//递归求解 
  40. 	}
  41.     public int numIslands(char[][] grid) {
  42.     	if(grid.length==0||grid[0].length==0)return 0;
  43.     	HashSet<Integer> islandLocation=new HashSet<Integer>();
  44. 		return findIslands(grid,islandLocation,0);
  45.     }

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

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

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


分析

方案一：中序遍历

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

  1. public class Solution {
  2.     public boolean isValidBST(TreeNode root) {
  3.     	//查找树的中序遍历为递增的
  4.     	if(root==null)return true;  
  5.     	TreeNode pre=null;//上一个节点
  6. 		Stack<TreeNode> stack=new Stack<TreeNode>();
  7. 		TreeNode p=root;
  8. 		while(p!=null||!stack.isEmpty()){
  9. 			while(p!=null){ 
  10. 				stack.push(p);
  11. 				p=p.left;
  12. 			}
  13. 			p=stack.pop();
  14. 			if(pre==null||pre.val<p.val){
  15. 				pre=p;
  16. 			}else{
  17. 				return false;
  18. 			} 
  19. 			if(p.right!=null){//处理右子树
  20. 				p=p.right;
  21. 			}else{//处理上一层
  22. 				p=null;
  23. 			} 
  24. 		} 
  25. 		return true;
  26.     }
  27. }
方案二：深度优先搜索 
  1. public class Solution {
  2.     public boolean isValidBST(TreeNode root) {
  3.         return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);//验证树中节点的值域
  4.     }
  5.     
  6.     public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
  7.         if (root == null) return true;
  8.         if (root.val >= maxVal || root.val <= minVal) return false;//检查根节点的值是否在值域内
  9.         //根据根节点的值，限定子树节点的值域
  10.         return isValidBST(root.left, minVal, root.val) 
  11.         		&& isValidBST(root.right, root.val, maxVal);
  12.     }
  13. }

分析

方案一：中序遍历

假如，正常的中序遍历结果为1,2,3,4,5,6,7,8。交换后的中序遍历结果变成1,7,3,4,5,6,2,8，我们如何找到两个颠倒位置的元素呢？
不难发现，重前往后第一个波峰，和从后往前第一个波谷。对于边界，假定最左边有个负无穷的元素，最右边有个正无穷的元素。
空间复杂度为O(n)，时间复杂度为O(n)。

  1. public class Solution {
  2.     public void recoverTree(TreeNode root) {
  3.     	//查找树的中序遍历为递增,先获取中序遍历，再定位交换位置
  4.     	if(root==null)return ;
  5.     	List<TreeNode> list=new ArrayList<TreeNode>();
  6. 		Stack<TreeNode> stack=new Stack<TreeNode>();
  7. 		TreeNode p=root;
  8. 		while(p!=null||!stack.isEmpty()){
  9. 			while(p!=null){ 
  10. 				stack.push(p);
  11. 				p=p.left;
  12. 			}
  13. 			p=stack.pop();
  14. 			list.add(p); 
  15. 			if(p.right!=null){//处理右子树
  16. 				p=p.right;
  17. 			}else{//处理上一层
  18. 				p=null;
  19. 			} 
  20. 		} 
  21. 		TreeNode firstNode=null;
  22. 		TreeNode secondNode=null;
  23. 		for(int i=0;i<list.size();i++){//从前往后找到第一个小大小
  24. 			if(i==0){
  25. 				if(list.get(i).val>list.get(i+1).val){
  26. 					firstNode=list.get(i);
  27. 					break;
  28. 				}
  29. 			}else{
  30. 				if(list.get(i-1).val<list.get(i).val&&list.get(i).val>list.get(i+1).val){
  31. 					firstNode=list.get(i);
  32. 					break;
  33. 				}
  34. 			}
  35. 		}
  36. 		for(int i=list.size()-1;i>=0;i--){//从后往前找到第一个大小大
  37. 			if(i==list.size()-1){
  38. 				if(list.get(i-1).val>list.get(i).val){
  39. 					secondNode=list.get(i);
  40. 					break;
  41. 				}
  42. 			}else{
  43. 				if(list.get(i-1).val>list.get(i).val&&list.get(i).val<list.get(i+1).val){
  44. 					secondNode=list.get(i);
  45. 					break;
  46. 				}
  47. 			}
  48. 		}
  49. 		int t=firstNode.val;firstNode.val=secondNode.val;secondNode.val=t;//交换
  50.     }
  51. }

方案二

方案一的解决思路非常直观，但是却需要O(n)的空间复杂度。如果能在中序遍历过程中标记错位的节点，空间复杂度就降为O(1)。

注：这里所说的O(1)空间复杂度，应该不考虑迭代过程中的栈空间，特此说明。


见讨论区：https://discuss.leetcode.com/topic/2200/an-elegent-o-n-time-complexity-and-o-1-space-complexity-algorithm/2

  1. public class Solution {
  2.     public void recoverTree(TreeNode root) {
  3.     	//查找树的中序遍历为递增,先获取中序遍历，再定位交换位置
  4.     	if(root==null)return ; 
  5. 		Stack<TreeNode> stack=new Stack<TreeNode>();  
  6. 		TreeNode firstNode=null;
  7. 		TreeNode secondNode=null; 
  8. 		TreeNode p=root;
  9. 		TreeNode preNode=null;//前驱
  10. 		TreeNode prePreNode=null;//前驱的前驱
  11. 		while(p!=null||!stack.isEmpty()){
  12. 			while(p!=null){ 
  13. 				stack.push(p);
  14. 				p=p.left;
  15. 			}
  16. 			p=stack.pop(); 
  17. 			if(preNode!=null){
  18. 				//标记第一个小大小
  19. 				if(firstNode==null&&preNode.val>p.val
  20. 						&&(prePreNode==null||prePreNode.val<preNode.val)){
  21. 					firstNode=preNode;
  22. 				}
  23. 				//标记最后一个大小大
  24. 				if(prePreNode!=null){
  25. 					if(prePreNode.val>preNode.val&&preNode.val<p.val){
  26. 						secondNode=preNode;
  27. 					}
  28. 				}
  29. 				if(p.right==null&&stack.isEmpty()){//最后一个节点特殊处理
  30. 					if(preNode.val>p.val){
  31. 						secondNode=p;
  32. 					}
  33. 				}
  34. 			} 
  35. 			prePreNode=preNode;preNode=p;
  36. 			if(p.right!=null){//处理右子树
  37. 				p=p.right;
  38. 			}else{//处理上一层
  39. 				p=null;
  40. 			}//这里为了阐述思路，其实可以简化为  p=p.right;
  41. 		}  
  42. 		int t=firstNode.val;firstNode.val=secondNode.val;secondNode.val=t;//交换
  43.     }
  44. }

  1. public class Solution {
  2.     public boolean isSameTree(TreeNode p, TreeNode q) {
  3.         if(p==null&&q==null)
  4.             return true;
  5.         if(p==null||q==null)
  6.             return false;
  7.         return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
  8.     }
  9. }

递归版 

  1. public class Solution {
  2.     public boolean isSymmetric(TreeNode root) { 
  3.         return root==null||isMirror(root.left,root.right);
  4.     }
  5.     private boolean isMirror(TreeNode p,TreeNode q){
  6.         if(p==null&&q==null)
  7.             return true;
  8.         if(p==null||q==null)
  9.             return false;
  10.         if(p.val!=q.val)
  11.             return false;
  12.         return isMirror(p.left,q.right)&&isMirror(p.right,q.left);
  13.     }
  14. }
跌代版 

  1. public class Solution {
  2. 	public boolean isSymmetric(TreeNode root) {
  3. 	    if(root==null)  return true;
  4. 	    
  5. 	    Stack<TreeNode> stack = new Stack<TreeNode>();
  6. 	    TreeNode left, right;
  7. 	    if(root.left!=null){
  8. 	        if(root.right==null) return false;
  9. 	        stack.push(root.left);
  10. 	        stack.push(root.right);
  11. 	    }
  12. 	    else if(root.right!=null){
  13. 	        return false;
  14. 	    }
  15. 	        
  16. 	    while(!stack.empty()){
  17. 	        if(stack.size()%2!=0)   return false;
  18. 	        right = stack.pop();
  19. 	        left = stack.pop();
  20. 	        if(right.val!=left.val) return false;
  21. 	        
  22. 	        if(left.left!=null){//左子树的左子树和右子树的右子树比较
  23. 	            if(right.right==null)   return false;
  24. 	            stack.push(left.left);
  25. 	            stack.push(right.right);
  26. 	        }
  27. 	        else if(right.right!=null){
  28. 	            return false;
  29. 	        }
  30. 	            
  31. 	        if(left.right!=null){//左子树的右子树和右子树的左子树比较
  32. 	            if(right.left==null)   return false;
  33. 	            stack.push(left.right);
  34. 	            stack.push(right.left);
  35. 	        }
  36. 	        else if(right.left!=null){
  37. 	            return false;
  38. 	        }
  39. 	    } 
  40. 	    return true;
  41. 	}
  42. }

分析

递归版

  1. public class Solution {
  2.     public int maxDepth(TreeNode root) {
  3.     	if(root==null)return 0;
  4.         return doMaxDepth(root);
  5.     }
  6.     public int doMaxDepth(TreeNode root) {
  7.     	if(root==null) return Integer.MIN_VALUE;
  8.     	if(root.left==null&&root.right==null) return 1;
  9.     	int leftDepth=doMaxDepth(root.left);
  10.     	int rightDepth=doMaxDepth(root.right);
  11.     	return 1+Math.max(leftDepth, rightDepth);
  12.     }
  13. }
迭代版

二叉树的后序遍历（深度优先遍历）可以访问到所有从根节点出发的路径，我们只需要在遍历过程中记录最大深度即可。

  1. public class Solution {
  2.     public int maxDepth(TreeNode root) { 
  3.         Map<TreeNode,Boolean> visit=new HashMap<TreeNode,Boolean>(); //标记节点访问情况
  4.         if(root==null) return 0;  
  5.         int max=1;
  6.         Stack<TreeNode> stack=new Stack<TreeNode>();  
  7.         TreeNode p=root;  
  8.         while(p!=null||!stack.isEmpty()){  
  9.             while(p!=null){   
  10.                 stack.push(p);  
  11.                 p=p.left;  
  12.             }  
  13.             max=Math.max(max, stack.size());//记录最大深度
  14.             p=stack.peek();  
  15.             if(p.right!=null){  
  16.                 if(visit.get(p)==null){  
  17.                     visit.put(p, true);
  18.                     p=p.right;  
  19.                 }  
  20.                 else{  
  21.                 	visit.remove(p);//移除
  22.                     stack.pop();  
  23.                     p=null;  
  24.                 }  
  25.             }else{    
  26.                 stack.pop();  
  27.                 p=null;  
  28.             }   
  29.         }   
  30.         return max;   
  31.     }  
  32. }

  1. public class Solution {
  2.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  3.     	int n=preorder.length;
  4. 		if(n==0)return null;
  5. 		return doBuildTree(preorder,0,n-1,inorder,0,n-1);
  6.         
  7.     }
  8.     public TreeNode doBuildTree(int[] preorder,int s1,int e1, int[] inorder,int s2,int e2){
  9. 		if(e1<s1)return null;
  10. 		int rootindex = 0;//根节点在中序序列中的位置
  11. 		for(int i=s2;i<=e2;i++){
  12. 			if(inorder[i]==preorder[s1]){
  13. 				rootindex=i;
  14. 				break;
  15. 			}
  16. 		}
  17. 		int leftCount=rootindex-s2;//左子树节点个数
  18. 		TreeNode root=new TreeNode(preorder[s1]);
  19. 		root.left=doBuildTree(preorder,s1+1,s1+leftCount,inorder,s2,rootindex-1);
  20. 		root.right=doBuildTree(preorder,s1+leftCount+1,e1,inorder,rootindex+1,e2);
  21.     	return root; 
  22.     }
  23. }

  1. public class Solution {
  2.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  3.     	int n=inorder.length;
  4. 		if(n==0)return null;
  5. 		return doBuildTree(inorder,0,n-1,postorder,0,n-1);
  6.     }
  7.     public TreeNode doBuildTree(int[] inorder,int s1,int e1, int[] postorder,int s2,int e2){
  8.   		if(e1<s1)return null;
  9.   		int rootindex = 0;
  10.   		for(int i=s1;i<=e1;i++){
  11.   			if(inorder[i]==postorder[e2]){
  12.   				rootindex=i;
  13.   				break;
  14.   			}
  15.   		}
  16.   		int leftCount=rootindex-s1;
  17.   		TreeNode root=new TreeNode(postorder[e2]);
  18.   		root.left=doBuildTree(inorder,s1,rootindex-1,postorder,s2,s2+leftCount-1);
  19.   		root.right=doBuildTree(inorder,rootindex+1,e1,postorder,s2+leftCount,e2-1);
  20.       	return root;
  21.     }
  22. }

  1. public class Solution {
  2.     public TreeNode sortedArrayToBST(int[] nums) {
  3.     	int n=nums.length;
  4.     	if(n==0)return null;
  5.     	return doSortedArrayToBST(nums,0,n-1);
  6.     }
  7.     public TreeNode doSortedArrayToBST(int[] nums,int start,int end) {
  8.     	if(end<start)return null;
  9.     	int mid=(start+end)/2;
  10.     	TreeNode root=new TreeNode(nums[mid]);
  11.     	root.left=doSortedArrayToBST(nums,start,mid-1);
  12.     	root.right=doSortedArrayToBST(nums,mid+1,end);
  13.     	return root;
  14.     }
  15. }

分析

基本思路不变。只是链表失去随机存取特性，寻找划分点的时候需要线性查找。

  1. public class Solution {
  2.     public TreeNode sortedListToBST(ListNode head) {
  3.     	ListNode p=head;
  4.     	int n=0;
  5.     	while(p!=null){
  6.     		p=p.next;
  7.     		n++;
  8.     	} 
  9. 		return buildBST(head,n); 
  10.     }
  11.     private TreeNode buildBST(ListNode head,int length){
  12.     	if(length==0)return null;
  13.     	TreeNode root=new TreeNode(-1);
  14.     	if(length==1){
  15.     		root.val=head.val;
  16.     		return root;
  17.     	}
  18.     	int index=1;
  19.     	int mid=(1+length)/2;
  20.     	ListNode midNode=head;
  21.     	while(index<mid){
  22.     		midNode=midNode.next;
  23.     		index++;
  24.     	}
  25.     	root.val=midNode.val;
  26.     	root.left=buildBST(head,mid-1);
  27.     	root.right=buildBST(midNode.next,length-mid); 
  28. 		return root; 
  29.     }
  30. }

  1. public class Solution {
  2.     public boolean isBalanced(TreeNode root) { 
  3. 		return lengthOfTree(root)!=-1; 
  4.     } 
  5.     private int lengthOfTree(TreeNode root){
  6.     	if(root==null) return 0; 
  7.     	int leftLength=lengthOfTree(root.left);
  8.     	int rightLength=lengthOfTree(root.right);
  9.     	if(leftLength==-1||rightLength==-1)return -1; 
  10.     	if(Math.abs(leftLength-rightLength)>1)return -1;
  11.     	return Math.max(leftLength, rightLength)+1;
  12.     }
  13. }

递归版 

  1. public class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if(root==null)return 0;
  4.         return doMinDepth(root);
  5.     }
  6.     public int doMinDepth(TreeNode root) {
  7.     	if(root==null) return Integer.MAX_VALUE;
  8.     	if(root.left==null&&root.right==null) return 1;
  9.     	int leftDepth=doMinDepth(root.left);
  10.     	int rightDepth=doMinDepth(root.right);
  11.     	return 1+Math.min(leftDepth, rightDepth);
  12.     }
  13. }
迭代版 

  1. public class Solution {
  2. 	public int minDepth(TreeNode root) {
  3. 		if (root == null)
  4. 			return 0;
  5. 		Stack<TreeNode> stack=new Stack<TreeNode>();
  6. 		 Map<TreeNode,Boolean> visit=new HashMap<TreeNode,Boolean>(); 
  7. 		int min=Integer.MAX_VALUE;
  8. 		TreeNode p=root;
  9. 		while(p!=null||!stack.isEmpty()){//后续遍历
  10. 			while(p!=null){
  11. 				stack.push(p);
  12. 				p=p.left;
  13. 			}
  14. 			p=stack.peek();
  15. 			if(p.left==null&&p.right==null){
  16. 				min=Math.min(min, stack.size());
  17. 			}
  18. 	        if(p.right!=null){//具有右子树  
  19. 	            if(visit.get(p)==null){//第一次出现在栈顶
  20. 	                visit.put(p, true);   
  21. 	                p=p.right;  
  22. 	            }  
  23. 	            else{//第二次出现在栈顶 
  24. 	            	visit.remove(p);
  25. 	                stack.pop();  
  26. 	                p=null;
  27. 	            }  
  28. 	        }else{    
  29. 	            stack.pop();  
  30. 	            p=null;  
  31. 	        }  
  32. 		}
  33. 		return min;
  34. 	}
  35. }

递归版 

  1. public class Solution {
  2.     public boolean hasPathSum(TreeNode root, int sum) {
  3.     	if(root==null) return false;
  4.     	if(root.left==null&&root.right==null&&sum==root.val){
  5.     		return true;
  6.     	}
  7. 		return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val); 
  8.     }
  9. }
迭代版 

  1. public class Solution {
  2. 	public boolean hasPathSum(TreeNode root, int sum) {
  3. 		if (root == null){
  4. 			return false;
  5. 		} 
  6. 		Stack<TreeNode> stack=new Stack<TreeNode>();
  7. 		 Map<TreeNode,Boolean> visit=new HashMap<TreeNode,Boolean>(); 
  8. 		int min=Integer.MAX_VALUE;
  9. 		TreeNode p=root;
  10. 		int currentSum=0;
  11. 		while(p!=null||!stack.isEmpty()){//后续遍历
  12. 			while(p!=null){
  13. 			    currentSum+=p.val;
  14. 				stack.push(p); 
  15. 				p=p.left; 
  16. 			}
  17. 			p=stack.peek();
  18. 			if(p.left==null&&p.right==null){
  19. 				if(currentSum==sum)return true;
  20. 			}
  21. 	        if(p.right!=null){//具有右子树  
  22. 	            if(visit.get(p)==null){//第一次出现在栈顶
  23. 	                visit.put(p, true);   
  24. 	                p=p.right;  
  25. 	            }  
  26. 	            else{//第二次出现在栈顶 
  27. 	            	visit.remove(p);
  28. 	                stack.pop(); 
  29. 	                currentSum-=p.val;
  30. 	                p=null;
  31. 	            }  
  32. 	        }else{    
  33. 	        	currentSum-=p.val;
  34. 	            stack.pop();  
  35. 	            p=null;  
  36. 	        }  
  37. 		}
  38. 		return false;
  39. 	}
  40. }


递归版

  1. public class Solution {
  2.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
  3.         List<List<Integer>> paths = new ArrayList<>();
  4.         pathSumUtil(paths, new ArrayList<Integer>(), root, sum);
  5.         return paths;
  6.     }
  7.     private void pathSumUtil(List<List<Integer>> paths, List<Integer> currList, TreeNode root, int sum) {
  8.         if (root == null) {
  9.             return;
  10.         }
  11.         sum = sum - root.val;
  12.         currList.add(root.val);
  13.         if (sum == 0 && root.left == null && root.right == null) {
  14.             paths.add(new ArrayList<>(currList));//copy
  15.         }
  16.         pathSumUtil(paths, new ArrayList<>(currList), root.left, sum);
  17.         pathSumUtil(paths, new ArrayList<>(currList), root.right, sum);
  18.     }
  19. }

迭代版

  1. public class Solution {
  2.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
  3.     	List<List<Integer>> res=new ArrayList<List<Integer>>();
  4. 		if(root==null) return res;
  5. 		Map<TreeNode,Boolean> visit=new HashMap<TreeNode,Boolean>();
  6. 		Stack<TreeNode> stack=new Stack<TreeNode>();
  7. 		int nowSum=0;
  8. 		TreeNode p=root;
  9. 		while(p!=null||!stack.isEmpty()){
  10. 			while(p!=null){ 
  11. 				stack.push(p);
  12. 				nowSum+=p.val;
  13. 				p=p.left;
  14. 			}
  15. 			p=stack.peek();
  16. 			if(p.left==null&&p.right==null&&sum==nowSum){
  17. 				List<Integer> r=new ArrayList<Integer>();
  18. 				for(Object i:stack.toArray())
  19. 					r.add((Integer)((TreeNode)i).val);
  20. 				res.add(r);
  21. 			}
  22. 			if(p.right!=null){
  23. 				if(visit.get(p)==null){
  24. 					visit.put(p, true);
  25. 					//第一次处理右子树
  26. 					p=p.right;
  27. 				}
  28. 				else{
  29. 					visit.remove(p);
  30. 					nowSum-=p.val;
  31. 					stack.pop(); 
  32. 					p=null;
  33. 				}
  34. 			}else{ 
  35. 				nowSum-=p.val;
  36. 				stack.pop();
  37. 				p=null;
  38. 			}
  39. 			
  40. 		} 
  41. 		return res;
  42.     }
  43. }

分析

递归版

  1. public class Solution {
  2.     public void flatten(TreeNode root) {
  3. 	    if (root == null)return;
  4. 	    doFlatten(root);
  5. 	}
  6. 	private TreeNode doFlatten(TreeNode root){//保证root!=null ，返回尾部节点
  7. 		if(root.left==null&&root.right==null)return root;
  8. 		if(root.left==null){
  9. 			TreeNode rightLast=doFlatten(root.right);
  10. 			root.right=root.right;
  11. 			root.left=null;
  12. 			return rightLast;
  13. 		} 
  14. 		if(root.right==null){
  15. 			TreeNode leftLast=doFlatten(root.left);
  16. 			root.right=root.left;
  17. 			root.left=null;
  18. 			return leftLast;
  19. 		}
  20. 		
  21. 		TreeNode leftLast=doFlatten(root.left); 
  22. 		TreeNode rightLast=doFlatten(root.right);
  23. 		leftLast.right=root.right;
  24. 		root.right=root.left; 
  25. 		root.left=null;
  26. 		return rightLast; 
  27. 	}
  28. }
迭代版

链表中的元素顺序即为先序遍历后的顺序。

  1. public class Solution {
  2. 	public void flatten(TreeNode root) {
  3. 	    if (root == null)return;
  4.         List<TreeNode> list=new ArrayList<TreeNode>();  
  5.         Stack<TreeNode> stack=new Stack<TreeNode>();  
  6.         TreeNode p=root;  
  7.         while(p!=null||!stack.isEmpty()){  
  8.             while(p!=null){  
  9.                 list.add(p);  
  10.                 stack.push(p);  
  11.                 p=p.left;  
  12.             }  
  13.             p=stack.pop();  
  14.             p=p.right;  
  15.         }   
  16.         for(int i=0;i<list.size();i++){
  17.         	TreeNode node=list.get(i);
  18.         	node.left=null;
  19.         	if(i==list.size()-1){
  20.         		node.right=null;
  21.         	}else{
  22.         		node.right=list.get(i+1);
  23.         	} 
  24.         }   
  25. 	}
  26. }


递归版

  1. public class Solution {
  2.     public void connect(TreeLinkNode root) {
  3.         if(root==null)
  4.             return;
  5.         if(root.left!=null){
  6.             root.left.next=root.right;//将当前节点的左右子树关联 
  7.             if(root.next != null)//将同一级别的相邻树关联
  8.                 root.right.next = root.next.left;
  9.         }        <pre name="code" class="java">        connect(root.right);
connect(root.left); }} 

 

 

迭代版
 

我们可以层次遍历树，遍历过程中将同一级别的节点串联起来。
 

 

  1. public class Solution {
  2.     public void connect(TreeLinkNode root) {
  3.         if(root==null) return;
  4.         LinkedList<TreeLinkNode> queue=new LinkedList<TreeLinkNode>();  
  5.         queue.add(root);   
  6.         while(!queue.isEmpty()){   
  7.         	ArrayList<TreeLinkNode> list=new ArrayList<TreeLinkNode>(queue);
  8.         	for(int i=0;i<list.size()-1;i++){//将同一级的节点串联
  9.         		list.get(i).next=list.get(i+1);
  10.         	}
  11.         	LinkedList<TreeLinkNode> nextQueue=new LinkedList<TreeLinkNode>();  
  12.             while(!queue.isEmpty()){  
  13.             	TreeLinkNode node=queue.poll();   
  14.                 if(node.left!=null)nextQueue.add(node.left);  
  15.                 if(node.right!=null)nextQueue.add(node.right);  
  16.             }   
  17.             queue=nextQueue;   
  18.         }  
  19.     }
  20. }
 
 

 

 


 
 

递归版
 

 

  1. public class Solution {
  2.     public void connect(TreeLinkNode root) {
  3.         if(root==null)
  4.             return;
  5.         //将当前节点的左右子树关联 
  6.         if(root.left!=null){//
  7.             root.left.next=root.right;
  8.         }
  9.         //将同一级别的相邻树关联
  10.         TreeLinkNode pre=root.right!=null?root.right:root.left;
  11.         TreeLinkNode nextTree=root.next;//相邻树
  12.         TreeLinkNode post=null;
  13.         while(nextTree!=null&&post==null){
  14.         	post=nextTree.left!=null?nextTree.left:nextTree.right;
  15.         	nextTree=nextTree.next;
  16.         } 
  17.         if(pre!=null){
  18.         	pre.next=post;
  19.         }
  20.         connect(root.right);//这里的顺序很关键
  21.         connect(root.left); //这里的顺序很关键
  22.     }
  23. }
 

 

迭代版（与上一题相同）
 

 

  1. public class Solution {
  2.     public void connect(TreeLinkNode root) {
  3.         if(root==null) return;
  4.         LinkedList<TreeLinkNode> queue=new LinkedList<TreeLinkNode>();  
  5.         queue.add(root);   
  6.         while(!queue.isEmpty()){   
  7.         	ArrayList<TreeLinkNode> list=new ArrayList<TreeLinkNode>(queue);
  8.         	for(int i=0;i<list.size()-1;i++){//将同一级的节点串联
  9.         		list.get(i).next=list.get(i+1);
  10.         	}
  11.         	LinkedList<TreeLinkNode> nextQueue=new LinkedList<TreeLinkNode>();  
  12.             while(!queue.isEmpty()){  
  13.             	TreeLinkNode node=queue.poll();   
  14.                 if(node.left!=null)nextQueue.add(node.left);  
  15.                 if(node.right!=null)nextQueue.add(node.right);  
  16.             }   
  17.             queue=nextQueue;   
  18.         }  
  19.     }
  20. }
 
 

 

  1. public class Solution {
  2.     public int maxPathSum(TreeNode root) {
  3.          List<Integer> res=doMaxPathSum(root);
  4.          return res.get(1);
  5.     }
  6.     //结果集中，第一个元素表示单向路径最大和，第二个元素表示最大路径和
  7.     public List<Integer> doMaxPathSum(TreeNode root){
  8.         List<Integer> res=new ArrayList<Integer>();
  9.         if(root==null){
  10.             res.add(Integer.MIN_VALUE);
  11.             res.add(Integer.MIN_VALUE);
  12.             return res;
  13.         }
  14.         List<Integer> leftRes=doMaxPathSum(root.left);
  15.         List<Integer> rightRes=doMaxPathSum(root.right);
  16.         int maxPath=root.val;
  17.         if(Math.max(leftRes.get(0),rightRes.get(0))>0) maxPath+=Math.max(leftRes.get(0),rightRes.get(0));
  18.         res.add(maxPath);
  19.         int maxSum=root.val;
  20.         if(leftRes.get(0)>0)maxSum+=leftRes.get(0);
  21.         if(rightRes.get(0)>0)maxSum+=rightRes.get(0);
  22.         res.add(Math.max(maxSum,Math.max(leftRes.get(1),rightRes.get(1))));
  23.         return res;
  24.     }
  25. }
 
 

 方案一 

 

 

 

  1. public class Solution {
  2.     public int sumNumbers(TreeNode root) {
  3.         return dfs(root, 0);
  4.     }
  5.     private int dfs(TreeNode root, int sum) {
  6.         if (root == null) return 0;
  7.         if (root.left == null && root.right == null)
  8.             return sum * 10 + root.val;
  9.         return dfs(root.left, sum * 10 + root.val) +
  10.             dfs(root.right, sum * 10 + root.val);
  11.     }
  12. }
 

 


 
 


 
 


 
 


 

                

        
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/484342
推荐阅读
相关标签
Copyright ©  2003-2013 www.wpsshop.cn  版权所有，并保留所有权利。

  
闽ICP备14008679号