解决所有二叉树路径问题

Notice: 二叉树不存在回溯问题！

非自顶向下问题

LeetCode中的代表问题：
124. 二叉树中的最大路径和
687. 最长同值路径
543. 二叉树的直径

这类问题的特点是：从任意节点到任意节点的路径，不必须从上到下。如下图所示，有两个 4 位于同一层，不存在上下关系。

该问题的模板是引入一个辅助函数 maxPath(node) 和一个全局变量 res。辅助函数的作用是求出以node节点为根结点的左侧最长路径和右侧最长路径，那么以该点为根结点的最长路径

最长路径 = 左侧最长路径+右侧最长路径

但值得注意的是，node向上层结点的返回值为左侧最长路径和右侧最长路径中较大的那个值。
因为左右两条路径只能选择一条（因为不能回头，只能二选一）。

ret = Math.max( 左侧最长路径，右侧最长路径 )

在主函数中只需从根结点开始DFS，遍历所有结点，操作每一个结点时，全局变量 res 进行更新，若左侧最长路径和右侧最长路径的和大于现在的 res 值，则更新res。

代码模板（Java）

int res = 0;
int maxPath(TreeNode node) //以node为路径起始点的最长路径
{
    if (node == null) return 0;
    int left = maxPath(node.left);  // 左侧路径长度
    int right= maxPath(node.right); // 右侧路径长度
    /**
	  根据不同题目条件
	  计算left和right的值
	**/
    res = max(res, left + right); //更新全局变量  
    return max(left, right);   //返回左右路径较长者
}
1
2
3
4
5
6
7
8
9
10
11
12
13