【二叉树】298. 二叉树最长连续序列

一、题目

1、题目描述

给你一棵指定的二叉树的根节点 root ，请你计算其中 最长连续序列路径 的长度。

最长连续序列路径 是依次递增 1 的路径。该路径，可以是从某个初始节点到树中任意节点，通过「父 - 子」关系连接而产生的任意路径。且必须从父节点到子节点，反过来是不可以的。

示例 1：
输入：root = [1,null,3,2,4,null,null,null,5]
输出：3
解释：当中，最长连续序列是 3-4-5 ，所以返回结果为 3 。

示例 2：
输入：root = [2,null,3,2,null,1]
输出：2
解释：当中，最长连续序列是 2-3 。注意，不是 3-2-1，所以返回 2 。

2、基础框架

• C++版本给出的基础框架如下：

3、原题链接

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

二、解题报告

1、思路分析

  $(1)$前序遍历，遍历过程中计算每个节点的最大序号（即所处的连续序列中的序号）
  $(2)$函数参数index代表当前节点的序号。

2、时间复杂度

3、代码详解

class Solution {
public:void dfs(TreeNode* root, int index, int& m) {if (root == nullptr) {return;}m = max(m, index);if (root->left != nullptr) {if (root->left->val == root->val + 1) {dfs(root->left, index + 1, m);} else {dfs(root->left, 1, m);}}if (root->right != nullptr){if (root->right->val == root->val + 1) {dfs(root->right, index + 1, m);} else {dfs(root->right, 1, m);}}}int longestConsecutive(TreeNode* root) {int m = 1;dfs(root, 1, m);return m;}
};

三、本题小知识