开发者社区> jianchao_li> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

[LeetCode] Binary Tree Longest Consecutive Sequence

简介: Problem Description: Given a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from so...
+关注继续查看

Problem Description:

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.


This post shares an elegant C++ solution, just in 4 lines. The code is as follows.

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int longestConsecutive(TreeNode* root) {
13         return longest(root, NULL, 0);
14     }
15 private:
16     int longest(TreeNode* now, TreeNode* parent, int len) {
17         if (!now) return len;
18         len = (parent && now->val == parent->val + 1) ? len + 1 : 1;
19         return max(len, max(longest(now->left, now, len), longest(now->right, now, len)));
20     }
21 };

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
算法题丨Longest Consecutive Sequence
描述 Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
995 0
[LeetCode] Binary Tree Zigzag Level Order Traversal
To be honest, I do not know whether this problem is designed to let you use stacks. Anyway, I don't. Here are my codes, both BFS and DFS version.
555 0
[LeetCode] Longest Consecutive Sequence
This problem is not very intuitive at first glance. However, the final idea should be very self-explanatory.
584 0
+关注
jianchao_li
热爱人工智能、机器学习和算法;截至2018年1月2日,LeetCode用户Most Reputation排名第2(https://discuss.leetcode.com/users?section=sort-reputation)
文章
问答
文章排行榜
最热
最新
相关电子书
更多
The Leaky Pipeline Problem: Making your Mark as a Woman in Big Data
立即下载
Lambda Processing for Near Time Search Indexing
立即下载
High-Performance Time Series
立即下载