LeetCode 549. 二叉树中最长的连续序列(树上DP)
> dp; int maxlen = 0;public: int longestConsecutive(TreeNode* root) { dfs(root); return maxlen; } void dfs(TreeNode* root) { if(!root) return; dfs(root->left); dfs(root->right); dp[root] = { 1,1};//上升,下降,的最大长度 if(root->left) { if(root->val == root->left->val+1)//左侧上升 dp[root][0] = max(dp[root][0], dp[root->left][0]+1); else if(root->val == root->left->val-1)//左侧下降 dp[root][1] = max(dp[root][1], dp[root->left][1]+1); } if(root->right) { if(root->val == root->right->val+1)//右侧上升 dp[root][0] = max(dp[root][0], dp[root->right][0]+1); else if(root->val == root->right->val-1)//右侧下降 dp[root][1] = max(dp[root][1], dp[root->right][1]+1); } maxlen = max(maxlen, dp[root][0]+dp[root][1]-1); //以该节点为升降的和,-1为该节点重复计算1次 }};
发布日期:2021-07-01 03:30:05
浏览次数:2
分类:技术文章
本文共 1429 字,大约阅读时间需要 4 分钟。
文章目录
1. 题目
给定一个二叉树,你需要找出二叉树中最长的连续序列路径的长度。
请注意,该路径可以是递增的或者是递减。
例如,[1,2,3,4] 和 [4,3,2,1] 都被认为是合法的,而路径 [1,2,4,3] 则不合法。 另一方面,路径可以是 子-父-子 顺序,并不一定是 父-子 顺序。示例 1:输入: 1 / \ 2 3输出: 2解释: 最长的连续路径是 [1, 2] 或者 [2, 1]。 示例 2:输入: 2 / \ 1 3输出: 3解释: 最长的连续路径是 [1, 2, 3] 或者 [3, 2, 1]。 注意: 树上所有节点的值都在 [-1e7, 1e7] 范围内。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-longest-consecutive-sequence-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
class Solution { unordered_map
44 ms 29.2 MB
我的CSDN
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
转载地址:https://michael.blog.csdn.net/article/details/107576568 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月29日 20时58分04秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Ant内置任务之symlink
2019-05-01
jface databinding:部分实现POJO对象的监测
2019-05-01
深入理解python--线程、进程与协程(1)
2019-05-01
Java--流重点总结初稿
2019-05-01
ImageView scaleType
2019-05-01
字符串的排序
2019-05-01
内存分配(mallloc,calloc,realloc,new)
2019-05-01
使用 Minidumps 和 Visual Studio .NET 进行崩溃后调试
2019-05-01
struts返回xml数据例子
2019-05-01
内存对齐详解
2019-05-01
秋招总结(一)-C++归纳
2019-05-01
秋招总结(三)-操作系统归纳
2019-05-01
带缓冲I/O 和不带缓冲I/O的区别与联系
2019-05-01
LINUX CP命令详解
2019-05-01
source insight快捷键及使用技巧
2019-05-01
映 射 ALT 键
2019-05-01
vim使用快捷键F4生成文件头注释、F5生成main函数模板、F6生成.h文件框架模板
2019-05-01
OV5620的视频驱动
2019-05-01