大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。
AlgoMooc 算法慕课网，每道题目都有动画和图片，致力于帮助每个程序员通过算法面试！
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题34. 二叉树中和为某一值的路径。
题目汇总链接：https://www.algomooc.com/jianzhioffer
一、题目描述
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
返回:
[
[5,4,11,2],
[5,8,4,5]
]
提示：
- 节点总数 <= 10000
二、题目解析
这道题目明确给出了路径的起始位置是在二叉树的根节点，直到延伸至叶子节点，如果想得到所有根节点到叶子结点的路径，需要遍历整棵树。
由于从根节点开始，所以采取前序遍历。
当用前序遍历访问到某一节点时，把当前节点添加到路径上，同时累加该节点的值，再进行一次判断：
- 如果当前节点为叶子节点，并且路径中所有节点的值之和等于输入的目标值，则当前路径符合要求，把路径加入到结果数组中；
- 如果当前节点为叶子节点，当路径中所有节点的值之和不等于输入的目标值，则需要回溯到它的父节点
- 如果当前节点不是叶子节点，则继续访问它的左右子节点。
三、动画描述
隐藏内容
此处内容需要权限查看
会员免费查看四、图片描述
五、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
// res 存放所有满足要求的路径
LinkedList<List<Integer>> res = new LinkedList<>();
// path 为正在遍历的路径
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
// 前序遍历二叉树
// 此时路径上的和为 0
findPath(root, sum,0);
return res;
}
// curPathSum 表示 path 路径上的和
void findPath(TreeNode root, int tar,int curPathSum) {
// 访问到叶子节点的时候返回
if(root == null) return;
// 把当前节点添加到路径上
path.add(root.val);
//同时累加该节点的值
curPathSum += root.val;
// 1、当前节点为叶子节点
// 2、路径中所有节点的值之和等于输入的目标值
// 当前路径符合要求，把路径加入到结果数组中
if(tar == curPathSum && root.left == null && root.right == null){
// 需要创建一个新的对象 path 来拷贝全局的 path 再添加到 res 中，因为全局的 path 一直在变化
// 如果直接添加全局的 path，会导致结果 res 中所有的 path 都是一样的
res.add(new LinkedList(path));
}
// 继续访问它的左子节点
findPath(root.left, tar,curPathSum);
// 继续访问它的右子节点
findPath(root.right, tar,curPathSum);
// 访问完当前节点 需要删除路径中最后一个节点，回退至父节点
path.removeLast();
}
}
六、复杂度分析
时间复杂度
时间复杂度为 O(N)。
空间复杂度
空间复杂度为 O(N)。
七、相关标签
- 搜索二叉树
- 深度优先搜索
