Longest path in a binary tree with just one bend

这个题大家有没有什么好的办法，类似于求二叉树的直径，但是多了一个one bend的限制，其实对这个限制条件的理解不是非常清楚，大面的意思就是二叉树的点尽量在一侧排列. 欢迎大家给指点一下.

how do you define "bend"?

doveonthewing 发表于 2013-12-20 23:11
how do you define "bend"?

目测应该是说从根到叶子的路径符合正则表达式：（(左)+(右)+）或者（(右)+(左)+）。。

动态规划。 记录每个点到叶子节点的without bend长度和只允许1个bend的长度， 状态方程很好写。

谢谢版主，我试着写一写

我的理解bend就是延伸方向的转换，比如之前结点一直向左延伸，然后从某个点开始向右延伸，这个是一种bend; 另外一种就是某个结点的左子树到这个结点再到右子树，这个是一种bend. 当然，对于第二
种情况，虽然没有parent指针可以用于回溯，但是因为要计算最长的路径，所以这个也可以考虑。不过如果理解为没有parent，无法回溯，就不算路径的话，那可以不考虑这一点. 否则，这一点也是需要考虑的