二叉树中和为目标值的路径

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：该题的一些思想和全排列有些相似