当前位置: 首页 > article >正文

力扣labuladong——一刷day44

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

  • 前言
  • 一、力扣298. 二叉树最长连续序列
  • 二、力扣988. 从叶结点开始的最小字符串
  • 三、力扣1022. 从根到叶的二进制数之和
  • 四、力扣1457. 二叉树中的伪回文路径
  • 五、力扣


前言


二叉树的递归分为「遍历」和「分解问题」两种思维模式,这道题需要用到「遍历」的思维。 代码看起来虽然多,但思路非常简单:用 path 维护递归遍历的路径,到达叶子节点的时候判断字典序最小的路径。 不要忘了在叶子节点的时候也要正确维护 path 变量,而且要把 StringBuilder 中的字符串反转才是目想要的答案。

一、力扣298. 二叉树最长连续序列

/**
 * 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 res = 1;
    public int longestConsecutive(TreeNode root) {
        fun(root, 1, Integer.MIN_VALUE);
        return res;
    }
    public void fun(TreeNode root, int len, int parentVal){
        if(root == null){
            return ;
        }
        if(root.val == parentVal+1){
            len ++;
        }else{
            len = 1;
        }
        res = Math.max(len, res);
        fun(root.left, len, root.val);
        fun(root.right,len,root.val);
    }
}

二、力扣988. 从叶结点开始的最小字符串

/**
 * 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 {
    String res = null;
    StringBuilder sb = new StringBuilder();
    public String smallestFromLeaf(TreeNode root) {
        fun(root);
        return res;
    }
    public void fun(TreeNode root){
        if(root == null){
            return;
        }
        sb.append((char)('a'+root.val));
        if(root.left == null && root.right == null){
            sb.reverse();
            String s = sb.toString();
            if(res == null || res.compareTo(s) > 0){
                res = s;
            }
            sb.reverse();
            sb.deleteCharAt(sb.length()-1);
            return;
        }
        fun(root.left);
        fun(root.right);
        sb.deleteCharAt(sb.length()-1);
    }
}

三、力扣1022. 从根到叶的二进制数之和

/**
 * 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 res = 0;
    int path = 0;
    public int sumRootToLeaf(TreeNode root) {
        fun(root);
        return res;
    }
    public void fun(TreeNode root){
        if(root == null){
            return;
        }
        path = path << 1 | root.val;
        if(root.left == null && root.right == null){
            res += path;

        }
        fun(root.left);
        fun(root.right);
        path = path >> 1;
    }
}

四、力扣1457. 二叉树中的伪回文路径

/**
 * 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 {
    List<Integer> path = new ArrayList<>();
    int[] arr = new int[10];
    int count = 0;
    public int pseudoPalindromicPaths (TreeNode root) {
        fun(root);
        return count;
    }
    public void fun(TreeNode root){
        if(root == null){
            return ;
        }
        path.add(root.val);
        arr[root.val] ++;
        if(root.left == null && root.right == null){
            int flag = 0;
            for(int i = 0; i < 10; i ++){
                if(arr[i]%2 == 1){
                    flag ++;
                }
            }
            if(flag <= 1){
                count ++;
            }
            arr[root.val] --;
            return;
        }
        fun(root.left);
        fun(root.right);
        path.remove(path.size()-1);
        arr[root.val] --;
    }
}

五、力扣


http://www.kler.cn/a/136094.html

相关文章:

  • minio参考官方文档实现多节点部署,基于ubuntu,还是失败了。。。。
  • 【Unity高级】如何动态调整物体透明度
  • 题海拾贝:力扣 231. 2 的幂
  • 从爱尔兰歌曲到莎士比亚:LSTM文本生成模型的优化之旅
  • Ubuntu中安装配置交叉编译工具并进行测试
  • VBA高级应用30例应用在Excel中的ListObject对象:向表中添加注释
  • 网络参考模型与标准协议(一)
  • ORA-00600 【3948】,ORA-00600 【3949】
  • 何时使用Elasticsearch而不是MySql?
  • 虚拟化逻辑架构: 创建KVM中的VM与实现VNC远程登录
  • 键盘控制ROS车运动
  • Linux 串口应用编程
  • 阿里国际站(直通车)
  • 【开题报告】基于SpringBoot的膳食营养健康网站的设计与实现
  • WebGoat通关攻略之 SQL Injection (intro)
  • 持续集成交付CICD:Jenkins Sharedlibrary 共享库
  • Java语言基础第四天
  • centos oracle11g开启归档模式
  • 下一代搜索引擎会什么?
  • 力扣贪心——跳跃游戏I和II
  • 【整顿C盘】pycharm、chrome等软件,缓存移动
  • 记一次线上bug排查-----SpringCloud Gateway组件 请求头accept-encoding导致响应结果乱码
  • pytho你-opencv划痕检测
  • 浅谈无线测温产品在菲律宾某工厂配电项目的应用
  • 手机照片误删解决方法分享
  • Qt中使用QNetworkAccessManager类发送https请求时状态码返回0