二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）二叉树路径节点关键值和等于

题目 【二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）】给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

文章图片
摘自LeetCode112 解题方法递归实现
目标sum值减去根节点的关键值，结果分别是根节点的左右子树的目标和。对左右子树递归调用函数，直到树叶节点为止。
代码

public boolean hasPathSum(TreeNode root, int sum) { if(null == root){//根节点为空，则返回false return false; } //直到树叶节点，如果关键值等于递归传入的sum值，则返回true if(null == root.left && null == root.right && root.val == sum){ return true; } //非树叶节点，对左右子树递归调用函数 //目标和要减去当前节点的关键值 boolean l = hasPathSum(root.left, sum - root.val); boolean r = hasPathSum(root.right, sum - root.val); return l || r; }

拓展题目如果题目要求不是判断是否存在这条路径，而是返回满足条件的路径？（LeetCode113）
拓展题目解析

与上一题思路一样，区别在于递归不再返回是否存在路径，而是需要记录遍历过的节点。
实现中我们在递归函数中传入用于存储遍历过节点的队列结构。
同时，因为递归是先遍历左子树再遍历右子树，只有左子树递归到树叶节点之后才会开始遍历右子树，那么我们可以仅仅使用同一个队列进行参数传递，在每个节点的左右子树递归遍历之后，移除当前的节点，这样可以减少不断构建新队列所带来的性能消耗。

拓展题目代码

public List> pathSum(TreeNode root, int sum) { List> result = new ArrayList<>(); List list = new ArrayList<>(); pathSumHelper(root, sum, result, list); return result; } //递归寻找存在的路径 private void pathSumHelper(TreeNode root, int sum, List> result, List list){ if(null == root){ return; } if(null == root.left && null == root.right && sum == root.val){ //遍历到树叶节点如果符合条件，存入队列中 list.add(root.val); //复制一个新的队列存入结果队列中 result.add(new ArrayList(list)); //移除当前节点，其他遍历分支继续使用这个队列 list.remove(list.size() - 1); return; } //遍历到非树叶节点，存入队列中 list.add(root.val); //递归左子树与右子树 pathSumHelper(root.left, sum - root.val, result, list); pathSumHelper(root.right, sum - root.val, result, list); //移除当前节点，其他遍历分支继续使用这个队列 list.remove(list.size() - 1); }