【寸铁的刷题笔记】树、dfs、bfs、回溯、递归(二)

大家好我是寸铁👊
金三银四，树、dfs、bfs、回溯、递归是必考的知识点✨
快跟着寸铁刷起来！面试顺利上岸👋
喜欢的小伙伴可以点点关注 💝

上期回顾

感谢大家的支持🌹🌹🌹
上期刷题笔记成功入选专栏第8名🔆

【寸铁的刷题笔记】树、dfs、bfs、回溯、递归(一)🎯

在这里插入图片描述

话不多说，开始新的篇章，继续刷起来💪

124. 二叉树中的最大路径和

思路

要求：返回其最大路径和
做法：路径和：枚举每个点作为起点,加上左右子树的值,取最大值即可。
先递归处理根节点的左右分支,向下走到底,把叶子节点的最大路径和取一个最大值。
回溯：向上回溯时,会计算上层根节点的路径和,继续取一个最大值。
返回：由于每个节点只能选一条路走，最大路径和下应该选择左右分支的最大值分支

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        //递归函数入口
        maxGain(root);
        //返回最大路径和
        return maxSum;
    }
    //题意分析:
    /*
    要求：返回其最大路径和
    做法：路径和：枚举每个点作为起点,加上左右子树的值,取最大值即可。
    先递归处理根节点的左右分支,向下走到底,把叶子节点的最大路径和取一个最大值。
    回溯：向上回溯时,会计算上层根节点的路径和,继续取一个最大值。
    返回：由于每个节点只能选一条路走，最大路径和下应该选择左右分支的最大值分支
    */
    public int maxGain(TreeNode node){
        if(node == null){
            return 0;
        }
        //向左递归,计算左子树的叶子节点的最大路径和
        //如果小于0 则不选该分支 因为选了后路径和反而更小
        int leftGain = Math.max(maxGain(node.left) , 0);
        //向右递归,计算右子树的叶子节点的最大路径和
       //如果小于0 则不选该分支 因为选了后路径和反而更小
        int rightGain = Math.max(maxGain(node.right) , 0);
        //计算
        //回溯时，会依次把上层非叶子节点做为根节点,计算其路径和
        int priceNewPath = node.val + leftGain + rightGain;
        //把每次计算的结果取一个max
        maxSum = Math.max(maxSum , priceNewPath);
        //返回一条较大路径 给上层节点继续计算路径和
        return node.val + Math.max(leftGain , rightGain);
    }
}

236. 二叉树的最近公共祖先

思路

核心思想：
不断向上层返回递归左、右子树的结果
再根据结果是否存在p、q 确定返回的最近公共祖先

模拟分析图

在这里插入图片描述

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //核心思想：
    //不断向上层返回递归左、右子树的结果
    //再根据结果是否存在p、q 确定返回的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //如果说根节点为空 则向上返回null即可
        if(root == null)return null;
        //这里是针对两种情况
        //一种是递归遍历时,遍历到的节点为p或者q则向上返回root
        //一种是p为当前的根节点,q为p所在树的后面节点出现,则直接向上返回root即可
        if(root == p || root == q)return root;
        //左、右、中
        //后序遍历 根据递归搜索到的左、右子树节点的情况进行判断
        //递归左子树
        TreeNode left = lowestCommonAncestor(root.left , p , q);
        //递归右子树 
        TreeNode right = lowestCommonAncestor(root.right , p , q);

        //中的逻辑
        //如果说左子树和右子树不为空
        //则当前的root就是最近公共祖先
        //向上返回即可
        if(left != null && right != null){
            return root;
        }else if(left != null && right == null){
            //说明 左子树为最近公共祖先 向上返回
            return left;
        }else if(left == null && right != null){
            //说明 右子树为最近公共祖先 向上返回
            return right;
        }else{
            return null;
        }
    }
}

102. 二叉树的层序遍历

考点

层序遍历、BFS

思路

思路：借助队列实现层序遍历,维护一个节点队列,记录队列的长度。
每次只弹出这一层的节点,把弹出节点添加到结果队列中。
再把弹出节点的左孩子、右孩子添加到节点队列中。
用于下一次节点队列节点的遍历与弹出。

代码


class Solution {
    /*
    思路：借助队列实现层序遍历,维护一个节点队列,记录队列的长度。
    每次只弹出这一层的节点,把弹出节点添加到结果队列中。
    再把弹出节点的左孩子、右孩子添加到节点队列中。
    用于下一次节点队列节点的遍历与弹出。
    */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root != null){
            Queue<TreeNode>queue = new LinkedList<>();
            queue.offer(root);
            int size;
            TreeNode node;
            while(!queue.isEmpty()){
                List<Integer>ans = new ArrayList<>();
                size = queue.size();
                while(size-- > 0){
                    node = queue.poll();
                    ans.add(node.val);
                    if(node.left != null)queue.offer(node.left);
                    if(node.right != null)queue.offer(node.right);
                }
                res.add(ans);
            }
        }
        return res;
    }
}

199. 二叉树的右视图

考点

层序遍历、BFS

思路

遍历每一层节点时，把他加入节点队列。获取当前队列的长度，弹出节点时，将其左右子孩子都加入队列中，用于下一轮队列的弹出，弹出最后一个节点时，直接将该节点的值添加到结果队列。

代码


class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        //创建一个队列用于存储二叉树右视图节点的值
        List<Integer> res = new ArrayList<>();
        if(root != null){
            //创建队列，用于层序遍历(bfs),存入每一行的点
            Queue<TreeNode>queue = new LinkedList<>();
            //先把根节点添加到队列中
            queue.offer(root);
            //队列的大小,放到外面,减少内存开销。
            int size;
            //存储从队列弹出来的节点,用于把弹出节点的值写入res队列中。
            TreeNode node;
            while(!queue.isEmpty()){
                size = queue.size();
                while(size -- > 0){
                    node = queue.poll();
                //不知道右视图看到的节点情况
                //索性每次弹出节点时,把节点的左孩子和右孩子都添加到队列中。
                    if(node.left != null)queue.offer(node.left);
                    if(node.right != null)queue.offer(node.right);

                //由于是从左到右遍历,入队,最后一个节点为最右侧节点
                //弹出最后一个节点时,把节点的值添加到res中。
                //注意这里是size-- 当size为1时,即为最后一个节点,--后为0。
                    if(size == 0)res.add(node.val);
                }
            }
        }
        return res;
    }
}

637. 二叉树的层平均值

考点

层序遍历、BFS

思路

思路：遍历每一层的节点,将其子孩子添加到队列，获取队列长度。
用临时变量计算每一层的节点的和值,再除以队列长度,最后添加到结果队列中即可。

代码


class Solution {
    /*
    思路：遍历每一层的节点,将其子孩子添加到队列，获取队列长度。
    用临时变量计算每一层的节点的和值,再除以队列长度,最后添加到结果队列中即可。
    */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double>res = new ArrayList<>();
        if(root != null){
            Queue<TreeNode>queue = new LinkedList<>();
            queue.offer(root);
            int size;
            TreeNode node;
            while(!queue.isEmpty()){
                double sum = 0;
                size = queue.size();
              for(int i = 0; i < size; i++){
                   node = queue.poll();
                   sum += node.val; 
                   if(node.left != null)queue.offer(node.left);
                   if(node.right != null)queue.offer(node.right);
                }
                res.add(sum / size);
            }                
            }
        return res;
    }
}

103. 二叉树的锯齿形层序遍历

考点

层序遍历、双端队列、BFS

思路

根据结果队列的层数，如果说层数是偶数(层数从0开始)，则进行从左到右遍历，即头插。如果说层数是奇数(层数从0开始)，则进行从右到左遍历，即尾插。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode>queue = new LinkedList<>(); //维护一个队列,存储节点
        List<List<Integer>>res = new ArrayList<>();//存储最后的结果
        if(root != null){
            queue.offer(root);
            int size;
            TreeNode node;
            while(!queue.isEmpty()){//只有队列不为空的时候,再进行弹出队列的节点操作。
                size = queue.size();//更新当前的队列size，确定弹出当前多少个节点用于下一轮的更新。
                List<Integer>ans = new LinkedList<>();//存储这一层的节点
                while(size -- > 0){
                    node = queue.poll();//弹出节点
                    //如果说层数(从0开始)为偶数,则进行尾插,即从左到右
                    if(res.size() % 2 == 0)ans.addLast(node.val);
                    //否则,进行头插,则是从右到左
                    else ans.addFirst(node.val);
                    //把弹出节点的左、右孩子入队
                    if(node.left != null)queue.offer(node.left);
                    if(node.right != null)queue.offer(node.right);
            }
            res.add(ans);//添加ans到最后的结果队列res中
            }
        }
        return res;
    }
}