LeetCode刷题实战298：二叉树最长连续序列

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 二叉树最长连续序列，我们先来看题面：

https://leetcode-cn.com/problems/binary-tree-longest-consecutive-sequence/

Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections .
The longest consecutive path need to be from parent to child (cannot be the reverse).

给你一棵指定的二叉树，请你计算它最长连续序列路径的长度。

该路径，可以是从某个初始结点到树中任意结点，通过「父 - 子」关系连接而产生的任意路径。

这个最长连续的路径，必须从父结点到子结点，反过来是不可以的。

示例

解题

找出左右结点中可能的更长的路径，进行保存

/**
* 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:
    void helper(TreeNode* root,int count,int& max_count){
        if(root==NULL){//终止条件
            return;
        }
        //若左结点不为空，则可以接着遍历
        if(root->left){
          //若左结点和根节点的值的关系满足连续，则调整长度
            if(root->val+1==root->left->val){
                max_count=max(max_count,count+1);
                helper(root->left,count+1,max_count);
            }
            else{
              //否则将长度重新置为1调整
                helper(root->left,1,max_count);
            }
        }
        //若右结点和根节点的值的关系满足连续，则调整长度
        if(root->right){
            if(root->val+1==root->right->val){
                max_count=max(max_count,count+1);
                helper(root->right,count+1,max_count);
            }
            else{
              //否则将长度重新置为1进行统计
                helper(root->right,1,max_count);
            }
        }
    }
    int longestConsecutive(TreeNode* root) {
        if(root==NULL){
            return 0;
        }
        int max_count=1;//初始长度
        helper(root,1,max_count);
        return max_count;
    }
};