devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

代码随想录（二叉树）

作者：小小林熬夜学编程 | 2024-05-31 10:44:00

赞

踩

代码随想录（二叉树）

二叉树的递归遍历

  1. class Solution {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3. 		List<Integer> list = new ArrayList<>();
  4. 		if(root==null) {
  5. 			return list;
  6. 		}else {
  7. 			traversal(list,root);
  8. 		}
  9.         return list;
  10. 	}
  11. 	public void traversal(List<Integer> list,TreeNode root) {
  12. 		if(root==null) {
  13. 			return;
  14. 		}
  15.         //前中后序调整一下下面的顺序即可
  16. 		list.add(root.val);
  17. 		traversal(list,root.left);
  18. 		traversal(list,root.right);
  19. 	}
  20. }

二叉树的迭代遍历

  1. 思路 以中序为扩展，其他的改变顺序即可  中序—左中右  栈—右中左
  2.  
  3. 1、先入栈根结点
  4.  
  5. 2、弹出第一个，因为我们每次先拿到的都是子树的中结点
  6.  
  7. 3、右结点入栈  中结点入栈并打上标记null  左结点入栈  
  8.  
  9. 4、遇见null结点则弹出两次 第二次的值入列表
  10. class Solution {
  11.     public List<Integer> inorderTraversal(TreeNode root) {
  12.         List<Integer> list = new ArrayList<>();
  13.         Deque<TreeNode> de = new LinkedList<>();
  14.         if(root==null){
  15.             return list;
  16.         }else{
  17.             de.addLast(root);
  18.         }
  19.         while(!de.isEmpty()){
  20.             TreeNode node = de.peekLast();
  21.             if(node!=null){  
  22.                 de.pollLast();
  23.                 if(node.right!=null){  //右
  24.                     de.addLast(node.right);
  25.                 }
  26.                 de.addLast(node);  //中
  27.                 de.addLast(null);
  28.                 if(node.left!=null){ //左
  29.                     de.addLast(node.left);
  30.                 }
  31.             }else{
  32.                 de.pollLast();
  33.                 node = de.peekLast();
  34.                 de.pollLast();
  35.                 list.add(node.val);
  36.             }
  37.         }
  38.         return list;
  39.     }
  40. }

二叉数的层序遍历（Leetcode102）

  1. 思路
  2.  
  3. 1、根结点入队  用int size = de.size() 可以了解到这一层有几个结点
  4.  
  5. 2、每层遍历到的结点考虑他的左右结点，如果有结点则入队 先左后右
  6.  
  7. 3、这一层遍历到的size个结点加入到arr中 这一层遍历完后再加入到list中
  8. public List<List<Integer>> levelOrder(TreeNode root) {
  9. 		List<List<Integer>> list = new ArrayList<>();
  10. 		Deque<TreeNode> de = new LinkedList<>();
  11. 		if(root==null) {
  12. 			return list;
  13. 		}else {
  14. 			de.add(root);
  15. 		}
  16. 		while(!de.isEmpty()) {
  17. 			int size = de.size();
  18. 			List<Integer> arr = new ArrayList<>();
  19. 			for(int i = 0;i<size;i++) { 
  20. 				TreeNode temp = de.pollFirst();
  21. 				if(temp.left!=null) {
  22. 					de.addLast(temp.left);
  23. 				}
  24. 				if(temp.right!=null) {
  25. 					de.addLast(temp.right);
  26. 				}
  27. 				arr.add(temp.val);
  28. 			}
  29. 			list.add(arr);
  30. 		}
  31. 		return list;
  32. 	}

二叉树的层序遍历2（Leetcode107）

  1. 思路 先层序遍历 再把顺序颠倒一下即可  Collections.reverse(list); 可以改变集合顺序
  2. public List<List<Integer>> levelOrderBottom(TreeNode root) {
  3. 		List<List<Integer>> list = new ArrayList<>();
  4. 		Deque<TreeNode> de = new LinkedList<>();
  5. 		if(root==null) {
  6. 			return list;
  7. 		}else {
  8. 			de.add(root);
  9. 		}
  10. 		while(!de.isEmpty()) {
  11. 			int size = de.size();
  12. 			List<Integer> arr = new ArrayList<>();
  13. 			while(size-->0) {
  14. 				TreeNode temp = de.pollFirst();
  15. 				if(temp.left!=null) {
  16. 					de.add(temp.left);
  17. 				}
  18. 				if(temp.right!=null) {
  19. 					de.add(temp.right);
  20. 				}
  21. 				arr.add(temp.val);
  22. 			}
  23. 			list.add(arr);
  24. 		}
  25. 		Collections.reverse(list);
  26. 		return list;
  27.     }

二叉树的右视图（Leetcode199）

  1. 思路：每次把每一层最后一个结点的值加入列表即可 也是层序
  2. public List<Integer> rightSideView(TreeNode root) {
  3. 		List<Integer> list = new ArrayList<>();
  4. 		Deque<TreeNode> de = new LinkedList<>();
  5. 		if(root==null) {
  6. 			return list;
  7. 		}else {
  8. 			de.add(root);
  9. 		}
  10. 		while(!de.isEmpty()) {
  11. 			int size = de.size();
  12. 			for(int i = 0;i<size;i++) {
  13. 				TreeNode temp = de.pollFirst();
  14. 				if(i==(size-1)){  //判断是不是当前层最后一个结点
  15. 					list.add(temp.val);
  16. 				}
  17. 				if(temp.left!=null) {
  18. 					de.addLast(temp.left);
  19. 				}
  20. 				if(temp.right!=null) {
  21. 					de.addLast(temp.right);
  22. 				}
  23. 				
  24. 			}
  25. 		}
  26. 		return list;
  27. 	}

二叉树的层平均值（Leetcode637） 

  1. class Solution {
  2.        public List<Double> averageOfLevels(TreeNode root) {
  3. 		List<Double> result = new LinkedList<>();
  4. 		Deque<TreeNode> de = new LinkedList<>();
  5. 		if(root==null) {
  6. 			return result;
  7. 		}
  8. 		de.add(root);
  9.         while(!de.isEmpty()){
  10.             int size = de.size();
  11.             int sum = size;
  12.             double num = 0;
  13.             while(size-->0){
  14.                 TreeNode temp = de.pollFirst();
  15.                 num += temp.val;
  16.                 if(temp.left!=null){
  17.                    de.addLast(temp.left);
  18.                }
  19.                if(temp.right!=null){
  20.                    de.addLast(temp.right);
  21.                }
  22.             }
  23.             double total = num/sum;
  24.             result.add(total);
  25.         }
  26. 		return result;
  27. }
  28. }

N叉树的层序遍历（Leetcode429）

  1.  
  2. class Solution {
  3.     public List<List<Integer>> levelOrder(Node root) {
  4.         List<List<Integer>> result = new LinkedList<>();
  5.         Deque<Node> de = new LinkedList<>();
  6.         if(root == null) {
  7.         	return result;
  8.         }
  9.         de.add(root);
  10.         while(!de.isEmpty()) {
  11.         	int size = de.size();
  12.         	List<Integer> list = new LinkedList<>();
  13.         	while(size-->0){
  14.                 Node temp = de.pollFirst();
  15.                 list.add(temp.val);
  16.                 if(temp.children!=null){  //判断是不是有子结点，有的话全部入队
  17.                     for(int i = 0;i<temp.children.size();i++){
  18.                         de.addLast(temp.children.get(i));
  19.                     }
  20.                 }
  21.         }
  22.         result.add(list);
  23.         }
  24.         return result;
  25.         
  26.         
  27.     }
  28. }

每个树行中找最大值（Leetcode515）

  1. class Solution {
  2.      public List<Integer> largestValues(TreeNode root) {
  3.         List<Integer> result = new LinkedList<>();
  4.         Deque<TreeNode> de = new LinkedList<>();
  5.         if(root==null) {
  6.         	return result;
  7.         }
  8.         de.add(root);
  9.         while(!de.isEmpty()){
  10.             int size = de.size();
  11.             int max = Integer.MIN_VALUE;
  12.             while(size-->0){
  13.                 TreeNode temp = de.pollFirst();
  14.                 max = max>temp.val?max:temp.val; //判断是不是当前层最大的
  15.                  if(temp.left!=null){
  16.                    de.addLast(temp.left);
  17.                }
  18.                if(temp.right!=null){
  19.                    de.addLast(temp.right);
  20.                }
  21.             }
  22.             result.add(max);
  23.         }
  24.         return result;
  25.    }
  26. }

 填充每个节点的下一个右侧节点（Leetcode116/117）

  1. 思路
  2.  
  3. 1、一先创建一个虚拟指针指向root ，用这个指针来操控即可，就不会影响影响到root
  4.  
  5. 2、层序遍历
  6.  
  7. 3、判断每层的最后一个都指向null 前面的按照队列顺序指向
  8. public Node connect(Node root) {
  9. 	     Deque<Node> de = new LinkedList<>();
  10. 	     if(root==null) {
  11. 	    	 return root;
  12. 	     }else {
  13. 	    	 Node cur = root;
  14. 	    	 de.add(cur);
  15. 	     }
  16. 	     while(!de.isEmpty()) {
  17. 	    	 int size = de.size();
  18. 	    	 for(int i = 0;i<size;i++) {
  19. 	    		 Node temp = de.pollFirst();
  20. 	    		 if(!de.isEmpty()&&de.peekFirst()!=null&&i!=(size-1)) { //除了最后一个节点外 弹出的指向弹出后的队首
  21. 	    			 temp.next = de.peekFirst();
  22. 	    		 }else {
  23. 	    			 temp.next = null;
  24. 	    		 }
  25. 	    		 if(temp.left!=null) {
  26. 	    			 de.addLast(temp.left);
  27. 	    		 }
  28. 	    		 if(temp.right!=null) {
  29. 	    			 de.addLast(temp.right);
  30. 	    		 }
  31. 	    		
  32. 	    	 }
  33. 	     }
  34. 	     return root;
  35. 	}

翻转二叉树（Leetcode226）

  1. 思路
  2.  
  3. 1、定义一个函数来交换左右节点
  4.  
  5. 2、遍历节点，每遍历一个节点交换一次
  6. class Solution {
  7. public TreeNode invertTree(TreeNode root) {
  8. 		Deque<TreeNode> de = new LinkedList<>();
  9. 		if(root==null) {
  10. 			return root;
  11. 		}else {
  12. 			de.add(root);
  13. 		}
  14. 		while(!de.isEmpty()) {
  15. 			int size = de.size();
  16. 			for(int i = 0;i<size;i++) {
  17. 				TreeNode temp = de.pollFirst();
  18. 				if(temp.left!=null) {
  19. 					de.addLast(temp.left);
  20. 				}
  21. 				if(temp.right!=null) {
  22. 					de.addLast(temp.right);
  23. 				}
  24. 				SwapNode(temp);
  25. 			}
  26. 		}
  27. 		return root;
  28. 	}
  29. 	public void SwapNode(TreeNode root) {
  30. 		TreeNode temp = root.left;
  31. 		root.left = root.right;
  32. 		root.right = temp;
  33. 	}
  34. }

对称二叉树（Leetcode101）

  1. 思路：
  2.  
  3. 1、根节点的左右节点入队
  4.  
  5. 2、每次判断左右节点的外侧和内侧节点是否相同
  6.  
  7. 3、左右节点的内外侧节点入队
  8. public boolean isSymmetric(TreeNode root) {
  9. 		Deque<TreeNode> de = new LinkedList<>();
  10.         if(root==null){
  11.             return true;
  12.         }else {
  13. 			de.add(root.left);
  14. 			de.add(root.right);
  15. 		}
  16. 		while(!de.isEmpty()) {
  17. 			TreeNode node1 = de.pollFirst();
  18. 			TreeNode node2 = de.pollFirst();
  19. 			if(node1==null&&node2!=null) {
  20. 				return false;
  21. 			}
  22. 			if(node2==null&&node1!=null) {
  23. 				return false;
  24. 			}
  25.             if(node1==null&&node2==null){
  26.                 continue;
  27.             }
  28. 			if(node1.val!=node2.val) {
  29. 				return false;
  30. 			}
  31. 			de.add(node1.left);
  32. 			de.add(node2.right);
  33. 			de.add(node1.right);
  34. 			de.add(node2.left);
  35. 		}
  36. 		return true;
  37.     }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/651874
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号