题目描述： 给定一个二叉树，你需要找出二叉树中最长的连续序列路径的长度。 请注意，该路径可以是递增的或者是递减。例如，[1,2,3,4] 和 [4,3,2,1] 都被认为是合法的，而路径 [1,2,4,3] 则不合法。另一方面，路径可以是 子-父-子 顺序，并不一定是 父-子 顺序。
示例 1: 输入: 输出: 2 解释: 最长的连续路径是 [1, 2] 或者 [2, 1]。
示例 2: 输入: 输出: 3 解释: 最长的连续路径是 [1, 2, 3] 或者 [3, 2, 1]。
方法1： 主要思路： （1）参考官方题解2； （2）对于每个结点，找出该节点下，从子节点到该结点的最长的增序列和减序列（除了为结点本身的情形之外，最长点的增减序列一定不是同一个子树下的序列），则该节点的最长的连续序列就是增序列加上减序列再减去1的结果； （3）最长的增，减序列的求取，可以更具左右子树的返回的最长的增减序列值进行求取；
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: //返回值是该根节点下的最长的增，减序列长度 pair<int,int> dec_find(TreeNode*root,int&max_len){ if(root==NULL){//叶子节点下为0,0 return {0,0}; } //分别找出左右子树的根节点的最长的增减序列 pair<int,int> left_len=dec_find(root->left,max_len); pair<int,int> right_len=dec_find(root->right,max_len); pair<int,int> len={1,1};//当前结点最长的增减序列为该节点本身，故为1,1 //若左子树不为空，则根据左子树的根节点的值和当前结点的值的关系，更新当前结点的最长增减序列的长度 if(root->left){ if(root->val==root->left->val+1){//若为增序列 len.first=left_len.first+1; } else if(root->val==root->left->val-1){//若为减序列 len.second=left_len.second+1; } } //同理，处理右子树和当前结点的关系 if(root->right){ if(root->val==root->right->val+1){ len.first=max(len.first,right_len.first+1);//注意这里使用的是max来获得更大的值 } else if(root->val==root->right->val-1){ len.second=max(len.second,right_len.second+1); } } //保存所有的可能的结点的最长的连续序列的长度 max_len=max(max_len,len.first+len.second-1); return len;//返回当前结点的最长的增减序列组成的pair } int longestConsecutive(TreeNode* root) { if(root==NULL){//处理特殊的情形 return 0; } //保存最长的连续序列的长度 int max_len=INT_MIN; //递归 dec_find(root,max_len); return max_len; } };