[LeetCode] 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).

For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is 3-4-5, so return 3.

   2
    \
     3
    / 
   2    
  / 
 1

Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

这道题让我们求二叉树的最长连续序列,关于二叉树的题基本都需要遍历树,而递归遍历写起来特别简单,下面这种解法是用到了递归版的先序遍历,我们对于每个遍历到的节点,我们看节点值是否比参数值(父节点值)大1,如果是则长度加1,否则长度重置为1,然后更新结果res,再递归调用左右子节点即可,参见代码如下: 

解法一:

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

下面这种写法是利用分治法的思想,对左右子节点分别处理,如果左子节点存在且节点值比其父节点值大1,则递归调用函数,如果节点值不是刚好大1,则递归调用重置了长度的函数,对于右子节点的处理情况和左子节点相同,参见代码如下:

解法二:

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

下面这种递归写法相当简洁,但是核心思想和上面两种方法并没有太大的区别,参见代码如下:

解法三:

class Solution {
public:
    int longestConsecutive(TreeNode* root) {
        return helper(root, NULL, 0);
    }
    int helper(TreeNode *root, TreeNode *p, int res) {
        if (!root) return res;
        res = (p && root->val == p->val + 1) ? res + 1 : 1;
        return max(res, max(helper(root->left, root, res), helper(root->right, root, res)));
    }
};

上面三种都是递归的写法,下面我们来看看迭代的方法,写法稍稍复杂一些,用的还是DFS的思想,以层序来遍历树,对于遍历到的节点,我们看其左右子节点有没有满足题意的,如果左子节点比其父节点大1,若右子节点存在,则排入queue,指针移到左子节点,反之若右子节点比其父节点大1,若左子节点存在,则排入queue,指针移到右子节点,依次类推直到queue为空,参见代码如下:

解法四:

class Solution {
public:
    int longestConsecutive(TreeNode* root) {
        if (!root) return 0;
        int res = 0;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int len = 1;
            TreeNode *t = q.front(); q.pop();
            while ((t->left && t->left->val == t->val + 1) || (t->right && t->right->val == t->val + 1)) {
                if (t->left && t->left->val == t->val + 1) {
                    if (t->right) q.push(t->right);
                    t = t->left;
                } else if (t->right && t->right->val == t->val + 1) {
                    if (t->left) q.push(t->left);
                    t = t->right;
                }
                ++len;
            }
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
            res = max(res, len);
        }
        return res;
    }
};

本文转自博客园Grandyang的博客,原文链接:二叉树最长连续序列[LeetCode] Binary Tree Longest Consecutive Sequence ,如需转载请自行联系原博主。

相关文章
|
30天前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
17 0
|
30天前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
13 0
|
30天前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
12 0
|
30天前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
11 0
|
30天前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
15 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
54 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
108 2
|
10天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
13 1
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口