devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Day15 二叉树

作者：你好赵伟 | 2024-08-07 16:00:55

赞

踩

Day15 二叉树

目录

层序遍历

107. 二叉树的层序遍历 II

 199. 二叉树的右视图

637. 二叉树的层平均值

429. N 叉树的层序遍历

 515. 在每个树行中找最大值

 116. 填充每个节点的下一个右侧节点指针

104. 二叉树的最大深度

111. 二叉树的最小深度

226. 翻转二叉树

101. 对称二叉树

层序遍历

107. 二叉树的层序遍历 II

状态：完成

思路：我这样写也可以做出来，最方便的办法肯定就是正向的层序遍历之后把答案翻转，还有一种不用翻转用LinkedList这个链表添加到头就行了。

  1. class Solution {
  2.     public List<List<Integer>> levelOrderBottom(TreeNode root) {
  3.         List<List<Integer>> list = new ArrayList<>();
  4.         if(root==null) return list;
  5.         Stack<TreeNode> stack=new Stack<>();
  6.         Queue<TreeNode> queue = new LinkedList<>();
  7.         queue.add(root);
  8.         while(queue.size()!=0){
  9.             int size =queue.size();
  10.             for(int i=0;i<size;i++){
  11.                 TreeNode temp =queue.poll();
  12.                 stack.push(temp);
  13.                 if(temp.right!=null) queue.add(temp.right);
  14.                 if(temp.left!=null) queue.add(temp.left);
  15.             }
  16.             stack.push(null);
  17.         }
  18.         stack.pop();
  19.         while(stack.size()>0){
  20.             List<Integer> tempList = new ArrayList<>();
  21.             TreeNode node=stack.pop(); 
  22.             while(node!=null){
  23.                 tempList.add(node.val);
  24.                 if(stack.size()==0) break;
  25.                 node=stack.pop();
  26.             }
  27.             list.add(tempList);
  28.         }
  29.         return list;
  30.     }
  31. }

 199. 二叉树的右视图

状态：完成

思路：其实这题就是层序遍历的最后一个值的集合，所以只要把每一层的最后一个节点写进结果数组中就可以。

  1. class Solution {
  2.     public List<Integer> rightSideView(TreeNode root) {
  3.         TreeNode node =root;
  4.         List<Integer> list = new ArrayList<>();
  5.         if(root==null) return list;
  6.         Queue<TreeNode> queue=new LinkedList<>();
  7.         queue.add(root);
  8.         while(queue.size()>0){
  9.             int size=queue.size();
  10.             for(int i=0;i<size;i++){
  11.                 node=queue.poll();
  12.                 if(node.left!=null) queue.add(node.left);
  13.                 if(node.right!=null) queue.add(node.right);
  14.             }
  15.             list.add(node.val);
  16.         }
  17.         return list;
  18.     }
  19. }

637. 二叉树的层平均值

状态：完成

思路：就是把每一层加起来除以每一层的个数

  1. class Solution {
  2.     public List<Double> averageOfLevels(TreeNode root) {
  3.         TreeNode node =root;
  4.         List<Double> list = new ArrayList<>();
  5.         if(root==null) return list;
  6.         Queue<TreeNode> queue=new LinkedList<>();
  7.         queue.add(root);
  8.         while(queue.size()>0){
  9.             int size=queue.size();
  10.             double sum=0;
  11.             double nums=0;
  12.             for(int i=0;i<size;i++){
  13.                 node=queue.poll();
  14.                 sum+=node.val;
  15.                 nums++;
  16.                 if(node.left!=null) queue.add(node.left);
  17.                 if(node.right!=null) queue.add(node.right);
  18.             }
  19.             list.add((double)sum/(double)nums);
  20.         }
  21.         return list;
  22.     }
  23. }

429. N 叉树的层序遍历

状态：完成

思路：把层序节点添加队列左右节点换成list的遍历

  1. class Solution {
  2.     public List<List<Integer>> levelOrder(Node root) {
  3.         List<List<Integer>> list=new ArrayList<>();
  4.         if(root==null) return list;
  5.         Queue<Node> queue=new LinkedList<>();
  6.         queue.add(root);
  7.         while(queue.size()>0){
  8.             int size=queue.size();
  9.             ArrayList<Integer> list2 = new ArrayList<>();
  10.             for(int i=0;i<size;i++){
  11.                 Node node= queue.poll();
  12.                 for(Node a:node.children){
  13.                     queue.add(a);
  14.                 }
  15.                 list2.add(node.val);
  16.             }
  17.             list.add(list2);
  18.         }
  19.         return list;
  20.     }
  21. }

 515. 在每个树行中找最大值

状态：完成

思路：层序遍历中把每一行的最大值找到放进去

  1. class Solution {
  2.     public List<Integer> largestValues(TreeNode root) {
  3.         List<Integer> list=new ArrayList<>();
  4.         if(root==null) return list;
  5.         Queue<TreeNode> queue=new LinkedList<>();
  6.         queue.add(root);
  7.         while(queue.size()>0){
  8.             int size=queue.size();
  9.             int max=Integer.MIN_VALUE;
  10.             for(int i=0;i<size;i++){
  11.                 TreeNode node= queue.poll();
  12.                 if(node.left!=null) queue.add(node.left);
  13.                 if(node.right!=null) queue.add(node.right);
  14.                 max=max>node.val?max:node.val;
  15.             }
  16.             list.add(max);
  17.         }
  18.         return list;
  19.     }
  20. }

 116. 填充每个节点的下一个右侧节点指针

状态：完成

思路：在层序遍历过程中链接右节点就可以了。

  1. class Solution {
  2.     public Node connect(Node root) {
  3.         List<List<Integer>> list=new ArrayList<>();
  4.         if(root==null) return root;
  5.         Queue<Node> queue=new LinkedList<>();
  6.         queue.add(root);
  7.         while(queue.size()>0){
  8.             int size=queue.size();
  9.             ArrayList<Integer> list2 = new ArrayList<>();
  10.             Node node=null;
  11.             for(int i=0;i<size;i++){
  12.                 if(node!=null){
  13.                     node.next=queue.poll();
  14.                     node= node.next;
  15.                 }else{
  16.                     node=queue.poll();
  17.                 }
  18.                 if(node.left!=null) queue.add(node.left);
  19.                 if(node.right!=null) queue.add(node.right);
  20.             }
  21.         }
  22.         return root;
  23.     }
  24. }

104. 二叉树的最大深度

状态：完成

思路：层序遍历算有多少层

  1. class Solution {
  2.     public int maxDepth(TreeNode root) {
  3.         if(root==null) return 0;
  4.         Queue<TreeNode> queue=new LinkedList<>();
  5.         queue.add(root);
  6.         int index=0;
  7.         while(queue.size()>0){
  8.             int size=queue.size();
  9.             for(int i=0;i<size;i++){
  10.                 TreeNode node= queue.poll();
  11.                 if(node.left!=null) queue.add(node.left);
  12.                 if(node.right!=null) queue.add(node.right);
  13.             }
  14.            index++;
  15.         }
  16.         return index;
  17.     }
  18. }

111. 二叉树的最小深度

状态：完成

思路：什么时候左右节点都是空的什么时候返回这时的层数+1。

  1. class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if(root==null) return 0;
  4.         Queue<TreeNode> queue=new LinkedList<>();
  5.         queue.add(root);
  6.         int index=0;
  7.         while(queue.size()>0){
  8.             int size=queue.size();
  9.             for(int i=0;i<size;i++){
  10.                 TreeNode node= queue.poll();
  11.                 if(node.left!=null) queue.add(node.left);
  12.                 if(node.right!=null) queue.add(node.right);
  13.                 if(node.left==null&&node.right==null){
  14.                     return index+1;
  15.                 }
  16.             }
  17.             index++;
  18.         }
  19.         return index;
  20.     }
  21. }

226. 翻转二叉树

层序遍历翻转二叉树：

  1. class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         if(root==null) return root;
  4.         Queue<TreeNode> queue=new LinkedList<>();
  5.         queue.add(root);
  6.         while(queue.size()>0){
  7.             int size=queue.size();
  8.             for(int i=0;i<size;i++){
  9.                 TreeNode node=queue.poll();
  10.                 TreeNode temp=node.left;
  11.                 node.left=node.right;
  12.                 node.right=temp;
  13.                 if(node.left!=null) queue.add(node.left);
  14.                 if(node.right!=null) queue.add(node.right);
  15.             }
  16.         }
  17.         return root;
  18.     }
  19. }

前、后序翻转：

  1. class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         if(root==null) return root;
  4.         TreeNode temp=root.left;
  5.         root.left=root.right;
  6.         root.right=temp;
  7.         invertTree(root.left);
  8.         invertTree(root.right);
  9.         return root;
  10.     }
  11. }

中序翻转时此时的左节点是右节点所以遍历原先右节点时是现在左节点

  1. class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         if(root==null) return root;
  4.         
  5.         invertTree(root.left);
  6.         TreeNode temp=root.left;
  7.         root.left=root.right;
  8.         root.right=temp;
  9.         invertTree(root.left);
  10.         return root;
  11.     }
  12. }

101. 对称二叉树

状态：层序遍历检测完成，后序遍历看讲解能理解意思

思路：层序遍历就是从层的两侧向中间去遍历，如果两侧的值不一样或者有空的值就肯定不是对称的。后序遍历感觉就是前序遍历的两个方向中左，中右这两个方向，周末休息的时候实现一下。

  1. class Solution {
  2.     public boolean isSymmetric(TreeNode root) {
  3.         List<List<Integer>> list=new ArrayList<>();
  4.         if(root==null) return false;
  5.         Queue<TreeNode> queue=new LinkedList<>();
  6.         if(root.left!=null&&root.right!=null){
  7.             queue.add(root.left);
  8.             queue.add(root.right);
  9.         }else{
  10.             if(root.left==null&&root.right==null){
  11.                 return true;
  12.             }
  13.             return false;
  14.         }
  15.         while(queue.size()>0){
  16.             int size=queue.size();
  17.             for(int i=0;i<size/2;i++){
  18.                 TreeNode left=queue.poll();
  19.                 TreeNode right=queue.poll();
  20.                 if(left.val!=right.val) return false;
  21.                 if(left.left!=null&&right.right!=null){
  22.                     queue.add(left.left);
  23.                     queue.add(right.right);
  24.                 }
  25.                 if(left.left==null&&right.right!=null) return false;
  26.                 if(left.left!=null&&right.right==null) return false;
  27.                 
  28.                 if(left.right!=null&&right.left!=null){
  29.                     queue.add(left.right);
  30.                     queue.add(right.left);
  31.                 }
  32.                 if(left.right==null&&right.left!=null) return false;
  33.                 if(left.right!=null&&right.left==null) return false;
  34.             }
  35.         }
  36.         return true;
  37.     }
  38. }

感想：二叉树之前没怎么做过，给我感觉挺灵活的，有时候没想到可以这样子做，而且很多数据结构也用到了二叉树，比如堆，周末我想总结一下java各个常用的数据结构的方法的时间复杂度。

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

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

  

闽ICP备14008679号