LeetCode 549. 二叉树中最长的连续序列（树上DP）

文章目录

• • 1. 题目
  • 2. 解题

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<TreeNode*, vector<int>> 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次} };

44 ms 29.2 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的LeetCode 549. 二叉树中最长的连续序列（树上DP）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。