Binary Tree Longest Consecutive Sequence II

自己没有思路,特别是那种贯穿左右子树的情况,不知道该如何计算,看了答案。发现自己好蠢,求的是长度数量又不需要求包含所有node的path,没有想象的那么难的,只是没有思考到点子上。

submit 1:有个小地方typo.


Screen Shot 2017-08-24 at 9.02.26 AM.png-269.7kB
Screen Shot 2017-08-24 at 9.02.26 AM.png-269.7kB

Screen Shot 2017-08-24 at 9.02.40 AM.png-75.9kB
Screen Shot 2017-08-24 at 9.02.40 AM.png-75.9kB

ac:


Screen Shot 2017-08-24 at 9.06.18 AM.png-208kB
Screen Shot 2017-08-24 at 9.06.18 AM.png-208kB

这道题的helper函数的思路是,从当前根节点出发,最长连续路径 = 左子树的最长递增路径 + 右子树的最长递减路径 - 1 或者 = 左子树的最长递减路径 + 右子树的最长递增路径 - 1,也就是incSeq + decSeq - 1

helper函数的返回值是一个int[]. int[0]表示的是从该根节点出发,最长连续递增路径incSeq; int1表示的是从该根节点出发,最长连续递减路径decSeq. 我们定义了一个成员变量maxVal来表示所求最长连续路径. 那么我们先看当前根节点左子树,如果左子树的val等于根节点的val + 1, 那么从根节点出发的最长递增路径长度就等于左子树的incSeq + 1, 也就是left[0] + 1; 如果左子树的val = 根节点val - 1,则根节点出发的decSeq就等于左子树的decSeq + 1, 也就是left1 + 1
右子树的情况和左子树类似,只是要注意取Math.min, 因为左子树那边更新过incSeq, decSeq, 所以右子树得到的值不一定是左右子树中的最值,必须要取最小值才行。maxVal的更新也是,要将incSeq+decSeq - 1递归时前面得到的maxVal取最小值。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容