双非二本找工作前的准备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一个新的List
            List<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;
    }
}