Lintcode376 Binary Tree Path Sum solution题解

【题目描述】

Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.

A valid path is from root node to any of the leaf nodes.

给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。

一个有效的路径，指的是从根节点到叶节点的路径。

【题目链接】

http://www.lintcode.com/en/problem/binary-tree-path-sum/

【题目解析】

对于root来说，最大路径有两种情况

1. 不通过root, 在左右两边的子树里
2. 通过root, 如果左child, 和右child通过他们的最大path > 0,就可以连到root上

然后比较三个

1. 左边子树里的最大path
2. 右边子树里的最大path
3. 通过root的最大path

注意,child return给上面的可以连的值应该是通过自己的path sum,而不一定是最大的， return 俩个值，maxSum, single

recursive, helper function

【参考答案】

http://www.jiuzhang.com/solutions/binary-tree-path-sum/