学渣刷题: [LintCode] 595 Binary Tree Longest Consecutive Sequence 解题报告
[LintCode] 595 Binary Tree Longest Consecutive Sequence 解题报告
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).
Example
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, not 3-2-1, so return 2.
思路
用分治法遍历整个树。同时维护一个最长序列的变量longest。
遍历每个节点的时候，测试一下加上这个节点的最长序列是多少，决定是否要更新longest。
遍历完整棵树，longest就是我们求的值。
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).
Example
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, not 3-2-1, so return 2.
思路
用分治法遍历整个树。同时维护一个最长序列的变量longest。
遍历每个节点的时候，测试一下加上这个节点的最长序列是多少，决定是否要更新longest。
遍历完整棵树，longest就是我们求的值。
Read full article from 学渣刷题: [LintCode] 595 Binary Tree Longest Consecutive Sequence 解题报告
No comments:
Post a Comment