二叉树中和为某一值的路径(剑指offer34)

题目

输入一颗二叉树和一个整数&＃xff0c;打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始一直到树的叶子节点形成的路径。

解题思路

先序遍历: 本题我采用的是先序遍历树的所有节点&＃xff0c;也就是按照根、左、右的顺序。
详细思路&＃xff1a; 由于本题目是一个将二叉树对应的路径给输出&＃xff0c;所有需要两个方法&＃xff0c;一个是专门负责进行递推&＃xff0c;将所有符合的节点都输出&＃xff0c;另一个就是负责将这个结果列表进行一个返回。
两个方法&＃xff1a;
pathSum(root,sum)函数&＃xff1a;

• 初始化&＃xff1a;结果列表res,路径列表path
• 返回值&＃xff1a;返回res即可

recur(root,tar)函数

• 递推参数&＃xff1a;当前节点root,当前目标值var
• 终止条件&＃xff1a;若节点为空&＃xff0c;则直接返回。
• 递推工作&＃xff1a;
  1.路径更新&＃xff1a; 将当前节点值 root.val 加入路径 path &＃xff1b;
  2.目标值更新&＃xff1a; tar &＃61; tar - root.val&＃xff08;即目标值 tar 从 sum 减至 0&＃xff09;&＃xff1b;
  3.路径记录&＃xff1a; 当 ① root 为叶节点 且 ② 路径和等于目标值 &＃xff0c;则将此路径 path 加入 res 。
  先序遍历&＃xff1a; 递归左 / 右子节点。
  4.路径恢复&＃xff1a; 向上回溯前&＃xff0c;需要将当前节点从路径 path 中删除&＃xff0c;即执行 path.pop()

代码

class Solution {LinkedList<List<Integer>> res &＃61; new LinkedList<>();//首先就是创建这样的一个包含右链表的链表&＃xff0c;因为返回的可能有多个列表LinkedList<Integer> path &＃61; new LinkedList<>();//这个就是单独派出的一个链表进行先序遍历 public List<List<Integer>> pathSum(TreeNode root, int sum) {recur(root, sum);return res;}void recur(TreeNode root, int tar) {if(root &＃61;&＃61; null) return;path.add(root.val);tar -&＃61; root.val;//这个就是用的减号&＃xff0c;使得对应的东西不断减去&＃xff0c;直到为0if(tar &＃61;&＃61; 0 && root.left &＃61;&＃61; null && root.right &＃61;&＃61; null)res.add(new LinkedList(path));recur(root.left, tar);recur(root.right, tar);path.removeLast();}
}

总结

本题的重要思路就是用到了递归&＃xff0c;通过第一次执行完成&＃xff0c;判断其是否达到了减去之后为0&＃xff0c;如果不为0&＃xff0c;那么选择其他路径。