LeetCode124: 给定一个非空二叉树,返回其最大路径和。本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
在样例1中,路径可以看成从节点3出发,沿着树的父子关系经过节点1到达节点2。例2中,路径可以看成从节点7出发,沿着树的父子关系经过节点20到达节点15
1 | /** |
利用深度优先搜索,沿着叶节点依次向上考查节点。如果要考查祖父节点,需要选择左子节点和右子节点中较大的一个。例如样例2中,如果考查节点-10,需要选择左子节点15。利用一个全局变量maxsum记录搜索过程中的最大值,对于路径和小于0的子树,直接返回0,也就是路径中不包含此子树的节点