​LeetCode刷题实战298:二叉树最长连续序列

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 二叉树最长连续序列,我们先来看题面:
https://leetcode-cn.com/problems/binary-tree-longest-consecutive-sequence/

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections .

The longest consecutive path need to be from parent to child (cannot be the reverse).

给你一棵指定的二叉树,请你计算它最长连续序列路径的长度。
该路径,可以是从某个初始结点到树中任意结点,通过「父 - 子」关系连接而产生的任意路径。
这个最长连续的路径,必须从父结点到子结点,反过来是不可以的。

示例

解题

找出左右结点中可能的更长的路径,进行保存

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void helper(TreeNode* root,int count,int& max_count){
        if(root==NULL){//终止条件
            return;
        }
        //若左结点不为空,则可以接着遍历
        if(root->left){
          //若左结点和根节点的值的关系满足连续,则调整长度
            if(root->val+1==root->left->val){
                max_count=max(max_count,count+1);
                helper(root->left,count+1,max_count);
            }
            else{
              //否则将长度重新置为1调整
                helper(root->left,1,max_count);
            }
        }
        //若右结点和根节点的值的关系满足连续,则调整长度
        if(root->right){
            if(root->val+1==root->right->val){
                max_count=max(max_count,count+1);
                helper(root->right,count+1,max_count);
            }
            else{
              //否则将长度重新置为1进行统计
                helper(root->right,1,max_count);
            }
        }
    }
    int longestConsecutive(TreeNode* root) {
        if(root==NULL){
            return 0;
        }
        int max_count=1;//初始长度
        helper(root,1,max_count);
        return max_count;
    }
};

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。
上期推文:
LeetCode1-280题汇总,希望对你有点帮助!
LeetCode刷题实战281:锯齿迭代器
LeetCode刷题实战282:给表达式添加运算符
LeetCode刷题实战283:移动零
LeetCode刷题实战284:顶端迭代器
LeetCode刷题实战285:二叉搜索树中的顺序后继
LeetCode刷题实战286:墙和门
LeetCode刷题实战287:寻找重复数
LeetCode刷题实战288:单词的唯一缩写
LeetCode刷题实战289:生命游戏
LeetCode刷题实战290:单词规律
LeetCode刷题实战291:单词规律II
LeetCode刷题实战292:Nim 游戏
LeetCode刷题实战293:翻转游戏
LeetCode刷题实战294:翻转游戏II
LeetCode刷题实战295:数据流的中位数
LeetCode刷题实战296:最佳的碰头地点
LeetCode刷题实战297:二叉树的序列化与反序列化
(0)

相关推荐

  • Leetcode l872. 叶子相似的 做题小结

    题目: 请考虑一棵二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 . 举个例子,如上图所示,给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树. 如果有两棵二叉树的叶值序 ...

  • Leetcode刷题 2021.01.19

    Leetcode刷题 2021.01.19 Leetcode1584 连接所有点的最小费用 Leetcode1376 通知所有员工所需的时间 Leetcode1637 两点之间不包含任何点的最宽垂直面 ...

  • (1条消息) 漫画:二叉树系列 第四讲(BST的查找)

    在上一节中,我们学习了二叉搜索树.那我们如何在二叉搜索树中查找一个元素呢?和普通的二叉树又有何不同?我们将在本节内容中进行学习! 下面看题:???????????? 01 第700题:二叉搜索树中的搜 ...

  • 每日一题 剑指offer(二叉树中和为某一值的路径)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • (1条消息) 万字长文!二叉树入门和刷题看这篇就够了!

    今天是小浩算法 "365刷题计划" 二叉树入门 - 整合篇.本篇作为入门整合篇,已经砍去难度较大的知识点,所有列出的内容,均为必须掌握.因为很长,写下目录: 二叉树是啥 二叉树的最 ...

  • ​LeetCode刷题实战128:最长连续序列

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战409:最长回文串

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战255:验证前序遍历序列二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战187:重复的DNA序列

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战257:二叉树的所有路径

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战236:二叉树的最近公共祖先

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战226:翻转二叉树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战297:二叉树的序列化与反序列化

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战145:二叉树的后序遍历

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...