LCR 153. 二叉树中和为目标值的路径
LCR 153. 二叉树中和为目标值的路径
参考题解
前言
该题考察二叉树中的回溯,使用先序遍历以及路径记录
先序遍历:根左右
路径记录:通过一个“中间人”(path
)来记录当前的路径和,当符合目标条件就赋值给res
递归函数–recur()
1、边界条件
root
为空的时候,直接返回
2、把root.val
加入到path
中,同时还要对tar
减去root.val
,即tar -= root.val
3、当root
是叶子节点,而且目标值tar
等于 0 的时候,即这一条path
是符合题目要求的,将path
加入到res
当中
- 注意:这里将
path
加入到res
需要新建一个对象,再加入到res
中,否则会有数据冲突,后续path
发生改变的时候,res
中的path
也会有改变,因为该path
变量始终都是同一个对象,在堆中的地址是一样的,因为才需要新建一个对象再加入到res
中
4、递归遍历左,右子树
5、由于已经遍历到了叶子节点,因此需要进行回溯,即path.pop()
public void recur(TreeNode root, int tar) {if(root == null) {return;}path.add(root.val); // 加入当前节点值到 pathtar -= root.val;if(tar == 0 && root.left == null && root.right == null) {res.add(new LinkedList<>(path));}recur(root.left, tar);recur(root.right, tar);path.removeLast();
}
pathTarget
函数
执行递归函数recur()
返回res
注意:path
和res
需要定义为全局变量
public List<List<Integer>> pathTarget(TreeNode root, int target) {recur(root, target);return res;
}
完整代码展示
class Solution {private final List<List<Integer>> res = new LinkedList<>();private final List<Integer> path = new LinkedList<>();public List<List<Integer>> pathTarget(TreeNode root, int target) {recur(root, target);return res;}public void recur(TreeNode root, int tar) {if(root == null) {return;}path.add(root.val); // 加入当前节点值到 pathtar -= root.val;if(tar == 0 && root.left == null && root.right == null) {res.add(new LinkedList<>(path));}recur(root.left, tar);recur(root.right, tar);path.removeLast();}
}
ps
:该题的一些思想和全排列有些相似