重庆网站建设网搜科技,成武县住房和城乡建设厅网站,2019年最好的国外vps,网站建设的目的和作用文章目录 一、题目1、题目描述2、基础框架3、原题链接 二、解题报告1、思路分析2、时间复杂度3、代码详解 三、本题小知识 一、题目
1、题目描述
给你一棵指定的二叉树的根节点 root #xff0c;请你计算其中 最长连续序列路径 的长度。
最长连续序列路径 是依次递增 1 的路… 文章目录 一、题目1、题目描述2、基础框架3、原题链接 二、解题报告1、思路分析2、时间复杂度3、代码详解 三、本题小知识 一、题目
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 ) (1) (1)前序遍历遍历过程中计算每个节点的最大序号即所处的连续序列中的序号 ( 2 ) (2) (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;}
};三、本题小知识
