1.86神华网站两学一做,艺术设计网,网站插件代码大全,商务网站建设的应用文章目录1. 题目2. 解题1. 题目
给定一个二叉树#xff0c;你需要找出二叉树中最长的连续序列路径的长度。
请注意#xff0c;该路径可以是递增的或者是递减。 例如#xff0c;[1,2,3,4] 和 [4,3,2,1] 都被认为是合法的#xff0c;而路径 [1,2,4,3] 则不合法。 另一方面你需要找出二叉树中最长的连续序列路径的长度。
请注意该路径可以是递增的或者是递减。 例如[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_mapTreeNode*, vectorint 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-val1)//左侧上升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-val1)//右侧上升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阿明一起加油、一起学习进步
