二叉树 层次遍历 及例题

二叉树层次遍历

• • • 二叉树层序遍历
    • • [102. 二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
      • 107.二叉树的层次遍历II
      • 199.二叉树的右视图
      • 637.二叉树的层平均值
      • 429.N叉树的层序遍历
      • 515.在每个树行中找最大值

二叉树层序遍历

102. 二叉树的层序遍历

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> re = new ArrayList<>();ArrayDeque<TreeNode> queue = new ArrayDeque<>();if (root == null) return re;queue.addFirst(root);while (!queue.isEmpty()) {ArrayList<Integer> arraylist = new ArrayList<>();int n = queue.size();//这个长度反应出来的是每一层的个数// 对这层的每一个进行处理，先进队的先处理，处理就是放值和放子节点for (int i = 0; i < n; i++) {root = queue.removeLast();arraylist.add(root.val);if(root.left!=null) queue.addFirst(root.left);if(root.right!=null) queue.addFirst(root.right);}//处理完一层后放到大list里re.add(arraylist);}return re;}
}

class Solution {public static List<List<Integer>> re = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {re=new ArrayList<List<Integer>>(); //力扣必须写这一下，要不然静态变量不更新，默认是一个Solution类在跑所有测试点Order(root,0);return re;}public static void Order(TreeNode node,int deep){if (node==null) return;//每个节点进来先deep++ 传入的deep是父节点的所在层数deep++;if (re.size()<deep){//一个size是一层，如果节点所在木有创建层，先创建这一层放进去ArrayList<Integer> arrayList = new ArrayList<>();re.add(arrayList);}//取出这个节点对于的这一层List<Integer> curCheng = re.get(deep - 1);curCheng.add(node.val);Order(node.left,deep);Order(node.right,deep);}
}

107.二叉树的层次遍历II

基于上一个题目

 List<List<Integer>> reQ= new ArrayList<>();for (int i=re.size();i>0;i--) {reQ.add(re.get(i-1));}return reQ;

199.二叉树的右视图

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> re = new ArrayList<>();ArrayDeque<TreeNode> queue = new ArrayDeque<>();if (root == null) return re;queue.addFirst(root);while (!queue.isEmpty()) {int n = queue.size();//这个长度反应出来的是每一层的个数// 对这层的每一个进行处理，先进队的先处理，处理就是放值和放子节点for (int i = 0; i < n; i++) {root = queue.removeLast();//判断if(i==n-1){re.add(root.val);}if(root.left!=null) queue.addFirst(root.left);if(root.right!=null) queue.addFirst(root.right);}}return re;}
}

正常一层一层遍历的基础上，判断是不是现在层的最后一个，如果是最后一个再加进去。因为有时候是看到左有时候是看到右，只能保证是每层的最后一个。

637.二叉树的层平均值

public List<Double> averageOfLevels(TreeNode root) {ArrayDeque<TreeNode> queue = new ArrayDeque<>();List<Double> re = new ArrayList<>();if (root==null) return re;queue.addFirst(root);while (!queue.isEmpty()){int size = queue.size();Double sum=0.0;for (int i=0;i<size;i++){TreeNode node = queue.removeLast();sum+=node.val;if (node.left!=null) queue.addFirst(node.left);if (node.right!=null) queue.addFirst(node.right);}double avg=sum/size;re.add(avg);}return re;
}

429.N叉树的层序遍历

class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> re = new ArrayList<>();if(root==null){return re;}ArrayDeque<Node> queue = new ArrayDeque<Node>();queue.add(root);while(!queue.isEmpty()){int n = queue.size();ArrayList<Integer> list = new ArrayList<>();for (int i =0; i<n;i++){Node node = queue.removeLast();list.add(node.val);for (Node child : node.children) {if (child!=null){queue.addFirst(child);}}}re.add(list);}return  re;}
}

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

class Solution {public List<Integer> largestValues(TreeNode root) {ArrayList<Integer> re = new ArrayList<>();ArrayDeque<TreeNode> queue = new ArrayDeque<>();if (root==null){return  re;}queue.add(root);while (!queue.isEmpty()){int n = queue.size();int max=Integer.MIN_VALUE;for (int i = 0; i < n; i++) {TreeNode node = queue.removeLast();max =Math.max(max,node.val);if (node.left!=null) queue.addFirst(node.left);if (node.right!=null) queue.addFirst(node.right);}re.add(max);}return  re;}
}

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

class Solution {public Node connect(Node root) {if(root==null) return null;ArrayDeque<Node> deque = new ArrayDeque<>();deque.addFirst(root);while (!deque.isEmpty()){int size = deque.size();Node per=null;for (int i = 0; i < size; i++) {Node node = deque.removeLast();if (node.left!=null) deque.addFirst(node.left);if (node.right!=null)deque.addFirst(node.right);if (per!=null){per.next=node;}per=node;}}return root;}
}

• 104.二叉树的最大深度

public class 二叉树的最大深度 {public int maxDepth(TreeNode root) {ArrayDeque<TreeNode> deque = new ArrayDeque<>();int re=0;if (root ==null){return re;}deque.addFirst(root);while (!deque.isEmpty()){int size = deque.size();re++;for (int i = 0; i < size; i++) {TreeNode node = deque.removeLast();if (node.left!=null) deque.addFirst(node.left);if (node.right!=null) deque.addFirst(node.right);}}return re;}
}

• 111.二叉树的最小深度

public class 二叉树的最小深度 {public int minDepth(TreeNode root) {ArrayDeque<TreeNode> deque = new ArrayDeque<>();int re=0;if (root==null){return re;}deque.addFirst(root);while (!deque.isEmpty()){re++;int n = deque.size();for (int i = 0; i < n; i++) {TreeNode node = deque.removeLast();if (node.right!=null) deque.addFirst(node.right);if (node.left!=null) deque.addFirst(node.left);if (node.right==null&&node.left==null){return re;}}}return re;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！