[Locked] Binary Tree Longest Consecutive Sequence

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.

分析:

  可看作是二分树上的动态规划,自底向上和自顶向下DFS均可

代码:

int height(TreeNode *node, int &totalmax) {
if(!node)
return ;
//自底向上DFS
int leftlength = height(node->left, totalmax), rightlength = height(node->right, totalmax);
if(node->left && node->left->val - != node->val)
leftlength = ;
if(node->right && node->right->val - != node->val)
rightlength = ;
int nodemax = max(leftlength + , rightlength + );
totalmax = max(totalmax, nodemax);
return nodemax;
}
int path(TreeNode *root) {
int totalmax = INT_MIN;
height(root, totalmax);
return totalmax;
}
上一篇:nginx方面的书籍资料链接


下一篇:项目一:第四天 1、快递员的条件分页查询-noSession,条件查询 2、快递员删除(逻辑删除) 3、基于Apache POI实现批量导入区域数据 a)Jquery OCUpload上传文件插件使用 b)Apache POI读取excel文件数据