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

Michael阿明

发布于 2021-02-19 10:22:26

5900

发布于 2021-02-19 10:22:26

文章被收录于专栏：Michael阿明学习之路

文章目录

- 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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/07/25 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树