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

代码随想录算法训练营第十五天 | 层序遍历 226.翻转二叉树 101.对称二叉树 2

作者：我家小花儿 | 2024-06-05 03:06:41

赞

踩

代码随想录算法训练营第十五天 | 层序遍历 226.翻转二叉树 101.对称二叉树 2

层序遍历 

看完本篇可以一口气刷十道题，试一试， 层序遍历并不难，大家可以很快刷了十道题。

题目链接/文章讲解/视频讲解：代码随想录

  • 102.二叉树的层序遍历(opens new window)
    1. public List<List<Integer>> levelOrder(TreeNode root) {
    2.         List<List<Integer>>  result = new ArrayList<List<Integer>>();
    3.         if(root == null){
    4.             return result;
    5.         }
    6.         Queue<TreeNode> que = new LinkedList<TreeNode>();
    7.         que.offer(root);
    8.         while(!que.isEmpty()){
    9.             List<Integer> itemList = new ArrayList<Integer>();
    10.             int len = que.size();
    11.             while (len > 0) {
    12.                 TreeNode tmpNode = que.poll();
    13.                 itemList.add(tmpNode.val);
    14.                 if (tmpNode.left != null) que.offer(tmpNode.left);
    15.                 if (tmpNode.right != null) que.offer(tmpNode.right);
    16.                 len--;
    17.             }
    18.             result.add(itemList);
    19.         }
    20.         return result;
    21. }
  • 107.二叉树的层次遍历II(opens new window)
    1.     public List<List<Integer>> solution1(TreeNode root) {
    2.         List<List<Integer>> list = new ArrayList<>();
    3.         Deque<TreeNode> que = new LinkedList<>();
    4.  
    5.         if (root == null) {
    6.             return list;
    7.         }
    8.  
    9.         que.offerLast(root);
    10.         while (!que.isEmpty()) {
    11.             List<Integer> levelList = new ArrayList<>();
    12.  
    13.             int levelSize = que.size();
    14.             for (int i = 0; i < levelSize; i++) {
    15.                 TreeNode peek = que.peekFirst();
    16.                 levelList.add(que.pollFirst().val);
    17.  
    18.                 if (peek.left != null) {
    19.                     que.offerLast(peek.left);
    20.                 }
    21.                 if (peek.right != null) {
    22.                     que.offerLast(peek.right);
    23.                 }
    24.             }
    25.             list.add(levelList);
    26.         }
    27.  
    28.         List<List<Integer>> result = new ArrayList<>();
    29.         for (int i = list.size() - 1; i >= 0; i-- ) {
    30.             result.add(list.get(i));
    31.         }
    32.  
    33.         return result;
    34.     }
  • 199.二叉树的右视图(opens new window)
    1. public List<Integer> rightSideView(TreeNode root) {
    2.         List<Integer> levelList = new ArrayList<>();
    3.         if(root == null){
    4.             return levelList;
    5.         }
    6.         Queue<TreeNode> que = new LinkedList<TreeNode>();
    7.         int temp = 0;
    8.         que.offer(root);
    9.         while(!que.isEmpty()){
    10.             int len = que.size();
    11.             while(len>0){
    12.                 TreeNode peek = que.poll();
    13.                 int val = peek.val;
    14.                 temp = val;
    15.                 if (peek.left != null) {
    16.                     que.offer(peek.left);
    17.                 }
    18.                 if (peek.right != null) {
    19.                     que.offer(peek.right);
    20.                 }
    21.                 len--;
    22.                 if(len==0){
    23.                     levelList.add(temp);
    24.                 }
    25.             }
    26.         }
    27.         return levelList;
    28.     }

  • 637. 二叉树的层平均值
    1.  public List<Double> averageOfLevels(TreeNode root) {
    2.         List<Double> levelList = new ArrayList<>();
    3.         if(root == null){
    4.             return levelList;
    5.         }
    6.         Queue<TreeNode> que = new LinkedList<TreeNode>();
    7.         que.offer(root);
    8.         while(!que.isEmpty()){
    9.             int len = que.size();
    10.             int len1 = len;
    11.             double temp = 0.0;
    12.             while(len>0){
    13.                 TreeNode peek = que.poll();
    14.                 int val = peek.val;
    15.                 temp += val;
    16.                 if (peek.left != null) {
    17.                     que.offer(peek.left);
    18.                 }
    19.                 if (peek.right != null) {
    20.                     que.offer(peek.right);
    21.                 }
    22.                 len--;
    23.                 if(len==0){
    24.                     levelList.add(temp/len1);
    25.                 }
    26.             }
    27.         }
    28.         return levelList;
    29.     }
  • 429.N叉树的层序遍历(opens new window)
    1. public List<List<Integer>> levelOrder(Node root) {
    2.         List<List<Integer>>  result = new ArrayList<List<Integer>>();
    3.         if(root == null){
    4.             return result;
    5.         }
    6.         Queue<Node> que = new LinkedList<Node>();
    7.         que.offer(root);
    8.         while(!que.isEmpty()){
    9.             List<Integer> itemList = new ArrayList<Integer>();
    10.             int len = que.size();
    11.             while (len > 0) {
    12.                 Node tmpNode = que.poll();
    13.                 itemList.add(tmpNode.val);
    14.                 for (int i = 0; i < tmpNode.children.size(); i++ ) {
    15.                     que.offer(tmpNode.children.get(i));
    16.                 }
    17.                 len--;
    18.             }
    19.             result.add(itemList);
    20.         }
    21.         return result;
    22.     }
  • 515.在每个树行中找最大值(opens new window)
    1. public List<Integer> largestValues(TreeNode root) {
    2.          List<Integer> levelList = new ArrayList<>();
    3.         if(root == null){
    4.             return levelList;
    5.         }
    6.         Queue<TreeNode> que = new LinkedList<TreeNode>();
    7.         que.offer(root);
    8.         while(!que.isEmpty()){
    9.             int len = que.size();
    10.             int len1 = len;
    11.             int temp = Integer.MIN_VALUE;
    12.             while(len>0){
    13.                 TreeNode peek = que.poll();
    14.                 int val = peek.val;
    15.                 temp = Math.max(temp,val);
    16.                 if (peek.left != null) {
    17.                     que.offer(peek.left);
    18.                 }
    19.                 if (peek.right != null) {
    20.                     que.offer(peek.right);
    21.                 }
    22.                 len--;
    23.                 if(len==0){
    24.                     levelList.add(temp);
    25.                 }
    26.             }
    27.         }
    28.         return levelList;
    29.     }
  • 116.填充每个节点的下一个右侧节点指针(opens new window)
    1.  public Node connect(Node root) {
    2.         if(root == null){
    3.             return null;
    4.         }
    5.         Queue<Node> que = new LinkedList<Node>();
    6.         que.offer(root);
    7.         while(!que.isEmpty()){
    8.             int len = que.size();
    9.             Node peek = que.poll();
    10.             if (peek.left != null) {
    11.                     que.offer(peek.left);
    12.                 }
    13.             if (peek.right != null) {
    14.                     que.offer(peek.right);
    15.                 }
    16.             for (int index = 1; index < len; index++){
    17.                 Node next = que.poll();
    18.                 if (next.left != null) {
    19.                     que.offer(next.left);
    20.                 }
    21.                 if (next.right != null) {
    22.                     que.offer(next.right);
    23.                 }
    24.                 peek.next = next;
    25.                 peek = next;
    26.             }
    27.         }
    28.         return root;
    29.     }
  • 117.填充每个节点的下一个右侧节点指针II(opens new window)
  • 同上
  • 104.二叉树的最大深度(opens new window)
    1. public int maxDepth(TreeNode root) {
    2.         if(root == null){
    3.             return 0;
    4.         }
    5.         int deep = Math.max(maxDepth(root.left),maxDepth(root.right));
    6.         return deep+1;
    7.     }
  • 111.二叉树的最小深度
    1.  public int minDepth(TreeNode root) {
    2.         if(root == null){
    3.             return 0;
    4.         }
    5.         if(root.left == null || root.right == null ){
    6.             return minDepth(root.left)+minDepth(root.right)+1;
    7.         }
    8.         return Math.min(minDepth(root.left),minDepth(root.right))+1;
    9.     }

 226.翻转二叉树 （优先掌握递归） 

这道题目 一些做过的同学 理解的也不够深入，建议大家先看我的视频讲解，无论做过没做过，都会有很大收获。

文章讲解/视频讲解：代码随想录

226. 翻转二叉树题目链接:226. 翻转二叉树

  1. public TreeNode invertTree(TreeNode root) {
  2.         resever(root);
  3.         return root;
  4.     }
  5.  
  6.     public void resever(TreeNode root){
  7.         if(root == null){
  8.             return;
  9.         }
  10.         resever(root.right);
  11.         resever(root.left);
  12.         TreeNode temp = root.right;
  13.         root.right =root.left;
  14.         root.left = temp;
  15.         
  16.     }

 101. 对称二叉树 （优先掌握递归）  

先看视频讲解，会更容易一些。 

题目链接:101. 对称二叉树

文章讲解/视频讲解：代码随想录

  1. public boolean isSymmetric(TreeNode root) {
  2.         return compare(root.left, root.right);
  3.     }
  4.  
  5.     private boolean compare(TreeNode left, TreeNode right) {
  6.  
  7.         if (left == null && right != null) {
  8.             return false;
  9.         }
  10.         if (left != null && right == null) {
  11.             return false;
  12.         }
  13.  
  14.         if (left == null && right == null) {
  15.             return true;
  16.         }
  17.         if (left.val != right.val) {
  18.             return false;
  19.         }
  20.         // 比较外侧
  21.         boolean compareOutside = compare(left.left, right.right);
  22.         // 比较内侧
  23.         boolean compareInside = compare(left.right, right.left);
  24.         return compareOutside && compareInside;
  25.  
  26. }

 拓展：

100. 相同的树

  1. public boolean isSameTree(TreeNode left, TreeNode right) {
  2.         if (left == null && right != null) {
  3.             return false;
  4.         }
  5.         if (left != null && right == null) {
  6.             return false;
  7.         }
  8.         if (left == null && right == null) {
  9.             return true;
  10.         }
  11.         if (left.val != right.val) {
  12.             return false;
  13.         }
  14.         return isSameTree(left.left, right.left) && isSameTree(left.right, right.right);
  15.  
  16.     }

572. 另一棵树的子树

  1. public boolean isSubtree(TreeNode root, TreeNode subRoot) {
  2.         if(root == null && subRoot == null){
  3.             return true;
  4.         }
  5.         if (root == null || subRoot == null) {
  6.             return false;
  7.         }
  8.         boolean ans2 = isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
  9.         return  isSametree(root, subRoot) || ans2;
  10.     }
  11.     public boolean isSametree(TreeNode s, TreeNode t) {
  12.         if(s == null && t == null) return true;
  13.         if(s == null || t == null) return false;
  14.         return s.val == t.val && isSametree(s.left,t.left) && isSametree(s.right,t.right);
  15.     }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/674545
推荐阅读
相关标签

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

  

闽ICP备14008679号