双非二本找工作前的准备day20（算法-二叉树系列）

本文主要是介绍双非二本找工作前的准备day20（算法-二叉树系列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

学习目标：

每天复习代码随想录上的题目1-2道算法（时间充足可以继续）

今日碎碎念：

1）今天开始是二叉树系列

2）出租屋里不知道干啥，看看书啊刷刷算法，打打游戏，学学技术啥的，不让自己太闲着才行。

3）天天都是吃外卖，不出门了都，后续等到9号回来之后继续开始整理八股（以复习为主）。

力扣刷题

算法

力扣102：102. 二叉树的层序遍历

dfs做法

class Solution {//结果集public List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {dfs(root,0);return res;}//dfs方式public void dfs(TreeNode node,Integer deep){if(node == null) return;//记录深度deep++;//开始将遍历到的层加入大结果集if(res.size() < deep){//解读该if代码块：如果走到下一层了，我们就需要new一个新的ListList<Integer> item = new ArrayList<>();//将新一层的小结果集放入大结果集res.add(item);}//开始dfs：通过deep找到对应层级的小结果集来存入遍历到的节点res.get(deep-1).add(node.val);dfs(node.left,deep);dfs(node.right,deep);}
}

bfs做法

class Solution {//结果集public List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {bfs(root);return res;}//bfs方式：队列的方式来迭代public void bfs(TreeNode node){if(node == null) return;Queue<TreeNode> que = new LinkedList<>();//bfs的做法有时候会比较dfs还要固定//先入根que.offer(node);while(!que.isEmpty()){List<Integer> list = new ArrayList<>();//记录队列长度，用于迭代int len = que.size();while(len > 0){//拿出队列中首层的节点TreeNode tmp = que.poll();list.add(tmp.val);//找左右if(tmp.left!=null) que.offer(tmp.left);if(tmp.right!=null) que.offer(tmp.right);len--;}res.add(list);}}
}

力扣107：107. 二叉树的层序遍历 II

dfs方法

class Solution {//最后进行反转即可public List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> levelOrderBottom(TreeNode root) {dfs(root,0);List<List<Integer>> result = new ArrayList<>();for (int i = res.size() - 1; i >= 0; i-- ) {result.add(res.get(i));}return result;}public void dfs(TreeNode node,Integer deep){if(node == null) return;//深度增加deep++;//新的一层就要增加小结果集if(res.size() < deep){List<Integer> item = new ArrayList<>();res.add(item);}//开始遍历左右//首先将该节点存入对应位置结果集res.get(deep-1).add(node.val);//找左右dfs(node.left,deep);dfs(node.right,deep);}
}

bfs做法

class Solution {//最后进行反转即可public List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> levelOrderBottom(TreeNode root) {bfs(root);List<List<Integer>> result = new ArrayList<>();for (int i = res.size() - 1; i >= 0; i-- ) {result.add(res.get(i));}return result;}public void bfs(TreeNode node){//为空直接返回if(node == null) return;Queue<TreeNode> que = new LinkedList<>();que.offer(node);//然后在while里面去不断迭代while(!que.isEmpty()){//小结果集List<Integer> list = new ArrayList<>();//bfs首先都得记录自己已经入队的节点数int size = que.size();for(int i = 0;i<size;i++){TreeNode tmp = que.poll();//拿出该节点后将该节点值入小结果集list.add(tmp.val);//去找左右if(tmp.left!=null) que.offer(tmp.left);if(tmp.right!=null) que.offer(tmp.right);}//当前层遍历完了，将小结果集加入大结果集res.add(list);}}
}

力扣199：199. 二叉树的右视图

bfs做法，这里就不再贴dfs做法了

class Solution {//思路还是很直接：用bfs做，只需要判断当前遍历到的是不是最右边的就可以public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if(root == null) return res;que.offer(root);while(!que.isEmpty()){int size = que.size();for(int i = 0;i<size;i++){TreeNode tmp = que.poll();//找左右if(tmp.left!=null) que.offer(tmp.left);if(tmp.right!=null) que.offer(tmp.right);//如何判断是右侧看到的：只要i走到了当前层的最后一个节点if(i == size - 1) res.add(tmp.val);}}return res;}
}

力扣637：637. 二叉树的层平均值

bfs做法，这里就不再贴dfs做法了

class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> res = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if(root == null) return res;que.offer(root);while(!que.isEmpty()){int size = que.size();double sum = 0.0;for(int i = 0;i<size;i++){TreeNode tmp = que.poll();//计算总值sum += tmp.val;//找左右if(tmp.left!=null) que.offer(tmp.left);if(tmp.right!=null) que.offer(tmp.right);}res.add(sum / size);}return res;}
}

力扣429：429. N 叉树的层序遍历

bfs做法，这里就不再贴dfs做法了

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public List<List<Integer>> res = new ArrayList<>();Deque<Node> que = new LinkedList<>();public List<List<Integer>> levelOrder(Node root) {//都通过bfs来做会快很多if(root == null) return res;que.offer(root);while(!que.isEmpty()){//记录当前大小int size = que.size();List<Integer> list = new LinkedList<>();for(int i = 0;i<size;i++){Node tmp = que.poll();list.add(tmp.val);//找孩子List<Node> children = tmp.children;//如果没孩子就继续即可if(children == null || children.size() == 0) continue;for(Node child : children){//有孩子就一个个找出来放到队列里面去if(child != null){que.offer(child);}}}//将该层加入大结果集res.add(list);}return res;}
}