二叉树的路径总和

第一题：是否存在路径和为目标值。

详见 leetcode 112。

给定二叉树和目标值，问从根节点到叶子节点求和，是否等于目标值，如果存在，返回true，否则返回 false。

解法：携带目标的 DFS 搜索。

第二题：是否存在路径和为目标值，输出所有路径。

详见 leetcode 113。

给定二叉树和目标值，问从根节点到叶子节点求和，是否等于目标值，如果存在，输出该路径，可能不止一个答案。

解法：携带目标，且记录路径的 DFS 搜索。

第三题：是否存在路径和为目标值，且不必从根到叶子。

详见 leetcode 473。

给定二叉树和目标值，问路径和是否等于目标值。

这里对路径要求：

1）不必从根节点开始，也不必从叶子节点结束

2）路径必须是向下的，即从父节点到子节点

解法：DFS 搜索过程中，记录路径的前缀和，

第四题：最大路径和

详见 leetcode 124。

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。