专栏首页Michael阿明学习之路LeetCode 298. 二叉树最长连续序列(自顶向下)

LeetCode 298. 二叉树最长连续序列(自顶向下)

1. 题目

给你一棵指定的二叉树,请你计算它最长连续序列路径的长度。

该路径,可以是从某个初始结点到树中任意结点,通过「父 - 子」关系连接而产生的任意路径。

这个最长连续的路径,必须从父结点到子结点,反过来是不可以的。

示例 1:
输入:

   1
    \
     3
    / \
   2   4
        \
         5

输出: 3
解析: 当中,最长连续序列是 3-4-5,所以返回结果为 3

示例 2:
输入:

   2
    \
     3
    / 
   2    
  / 
 1

输出: 2 
解析: 当中,最长连续序列是 2-3。注意,不是 3-2-1,所以返回 2。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-longest-consecutive-sequence 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

class Solution {
	int maxlen = 1;
public:
    int longestConsecutive(TreeNode* root) {
    	if(!root) return 0;
    	dfs(root, 1);
    	return maxlen;
    }
    void dfs(TreeNode* root, int len)
    {
    	if(!root) return;
    	maxlen = max(maxlen, len);
    	if(root->left)
    	{
    		if(root->val+1 == root->left->val)
    			dfs(root->left, len+1);//满足连续,长度+1
    		else
    			dfs(root->left, 1);//不满足,从新开始
    	}
    	if(root->right)
    	{
    		if(root->val+1 == root->right->val)
    			dfs(root->right, len+1);
    		else
    			dfs(root->right, 1);
    	}
    }
};

68 ms 33.3 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 222. 完全二叉树的节点个数(二分查找)

    说明: 完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底...

    Michael阿明
  • 剑指Offer - 面试题54. 二叉搜索树的第k大节点(二叉树循环遍历)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kd...

    Michael阿明
  • LeetCode 663. 均匀树划分(树形DP)

    给定一棵有 n 个结点的二叉树,你的任务是检查是否可以通过去掉树上的一条边将树分成两棵,且这两棵树结点之和相等。

    Michael阿明
  • LeetCode 663. 均匀树划分(树形DP)

    给定一棵有 n 个结点的二叉树,你的任务是检查是否可以通过去掉树上的一条边将树分成两棵,且这两棵树结点之和相等。

    Michael阿明
  • 360开源的Qconf配置同步工具使用记录

    我是攻城师
  • 【剑指offer】33.二叉树镜像

    可以看到首先对根节点的左右进行翻转。 再递归的对左子树,以及右子树进行翻转。 之前讲过,链表的题目分为四个步骤:连过来、指针走、断后路、调状态。 二涉及到树的...

    Leetcode名企之路
  • 附012.Kubeadm部署高可用Kubernetes

    Kubernetes的高可用主要指的是控制平面的高可用,即指多套Master节点组件和Etcd组件,工作节点通过负载均衡连接到各Master。HA有通常有如下两...

    木二
  • CentOS7设置IP地址

    Step1:切换至root用户 在linux下,root用户是最高级用户。我们在修改IP地址之前,需要切换至root用户才有权限操作。 ? Step2:进...

    似水的流年
  • 介绍linux下利用编译bash设置root账号共用的权限审计设置

    在日常运维工作中,公司不同人员(一般是运维人员)共用root账号登录linux服务器进行维护管理,在不健全的账户权限审计制度下,一旦出现问题,就很难找出源头,甚...

    洗尽了浮华
  • Django REST framework+Vue 打造生鲜超市(十一) 十二、支付宝沙箱环境配置

    十二、支付宝沙箱环境配置 12.1.创建应用 进入蚂蚁金服开放平台(https://open.alipay.com/platform/home.htm),登录后...

    zhang_derek

扫码关注云+社区

领取腾讯云代金券