614. 二叉树的最长连续子序列 II

给定一棵二叉树，找到最长连续序列路径的长度。

路径起点跟终点可以为二叉树的任意节点。

样例

1

/ \

2 0

/

3

返回 4 // 0-1-2-3

思路：需要注意最后得到的结果必然由一半从下往上增加，另一半从下往上减小的两部分组成。所以对于每个节点都需要计算这两个值。因为需要返回两个值，所以自定义了一个类ReturnInfo，其中的longest_up表示以当前根节点为末节点从下往上增长的最长连续数量，longest_down类似，关键是要理解连续，以及在每个节点的处理细节.

1 /** 2  * Definition of TreeNode: 3  * class TreeNode { 4  * public: 5  *     int val; 6  *     TreeNode *left, *right; 7  *     TreeNode(int val) { 8  *         this->val = val; 9  *         this->left = this->right = NULL;10  *     }11  * }12  */13 14 class ReturnInfo{15 public:16     int longest_up;17     int longest_down;18     ReturnInfo(int up,int down):longest_up(up),longest_down(down){};19 }20 21 22 class Solution {23 public:24     /**25      * @param root: the root of binary tree26      * @return: the length of the longest consecutive sequence path27      */28     int longestConsecutive2(TreeNode * root) {29         // write your code here30         longestInfo(root);31         return longest;32     }33 34     ReturnInfo longestInfo(TreeNode * root){35         if(root == nullptr) return ReturnInfo(0,0);//nullptr返回(0,0)36         int up = 1;//默认只有根节点，初始化为137         int down = 1;38         ReturnInfo tempL = longestInfo(root->left);//左右节点的连续信息39         ReturnInfo tempR = longestInfo(root->right);40 41         if(root->left){42             if(root->left->val == root->val - 1) up = max(up,tempL.longest_up+1);//左子树是否连续进行更新43             if(root->left->val == root->val + 1) down = max(down,tempL.longest_down+1);44         }45         46         if(root->right){47             if(root->right->val == root->val - 1) up = max(up,tempR.longest_up+1);//右子树处理48             if(root->right->val == root->val + 1) down = max(down,tempR.longest_down+1);49         }50         51         longest = max(longest,up+down-1);//以当前root为最高点的连续数字最多数量，仔细想想就是up+down-1。52         return ReturnInfo(up,down);53     }54     55 private:56     int longest = 0;57 };