剑指Offer:二叉树中和为某一值的路径

题目

输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数target的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

1
2
3
4
5
    10
/ \
5 12
/ \
4 7

分析

我们以上图为例来分析(求和为22的所有路径):

由于路径是从根节点出发,到叶子节点结束。也就是说路径总是以根节点为起始点,因此我们可以用前序遍历来遍历根节点。

在上图中,在访问10节点之后,就会访问节点5 。因为该二叉树中没有指向父节点的指针,所以在访问节点5的时候我们并不知道前面都经历了哪些节点。如果我们每遍历一个节点就从target身上减去当前节点的val值,接下来遍历到节点4时,我们再从target身上减去节点4的val值。这时候已经到达叶节点了,但是target的值并不为0,因此不是符合要求的路径。

我们接着去遍历其他的节点,在遍历下一个节点之前,先要从节点4回到节点5,再去遍历节点5的右子节点7. 值得注意的是,当回到节点5的时候,由于节点4已经不再前往节点7的路径上了,需要将节点4从路径中删除。接下来访问节点7的时候在把节点加入到路径中此时路径中有三个节点10,5,7.和刚好为22,是一条符合要求的路径。

我们最后要遍历的节点是12,在遍历这个节点之前需要先经过节点5回到节点10.同样的每次当从子节点回到父节点的时候需要从路径中删除子节点,最后从节点10到节点12的路径上只有两个节点10,12,他们的和也是22,所以这也是一条符合要求的路径。

通过上面的分析我们可以发现,当用前序遍历的方式访问到某一节点的时候我们需要把该节点加入路径,并累加该节点的值。如果该节点是叶子节点,并且路径上的节点值的和刚好等于输入的整数,则当前路径符合要求。

如果当前节点不是叶子节点,继续访问它的叶子节点。

当前节点访问结束后,递归会自动回到它的父节点。因此,我们在函数的退出之前要在路径上删除当前节点并减去当前节点的值,以确保返回父节点时路径刚好是从根节点到父节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private ArrayList<ArrayList<Integer>> arrayList = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> array = new ArrayList<Integer>();

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {

if (root == null)
return arrayList;
array.add(root.val);
target -= root.val;
if (0 == target && root.left==null && root.right==null) {
arrayList.add(new ArrayList<>(array));
}
FindPath(root.left, target);
FindPath(root.right, target);
array.remove(array.size()-1);
return arrayList;
}
}