【剑指Offer】34.二叉树中和为某一值的路径(二)

题目

输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

如二叉树root为{10,5,12,4,7},expectNumber为22

则合法路径有[[10,5,7],[10,12]]

数据范围:

树中节点总数在范围 [0, 5000] 内

-1000 <= 节点值 <= 1000

-1000 <= expectNumber <= 1000

示例1

输入：{10,5,12,4,7},22

返回值：[[10,5,7],[10,12]]

说明：返回[[10,12],[10,5,7]]也是对的

示例2

输入：{10,5,12,4,7},15

返回值：[]

示例3

输入：{2,3},0

返回值：[]

示例4

输入：{1,3,4},7

返回值：[]

解答

源代码

import java.util.*;
 
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param target int整型 
     * @return int整型ArrayList>
     */
    public ArrayList> FindPath(TreeNode root, int target) {
        // write code here
        ArrayList> res = new ArrayList>();
        ArrayList combine = new ArrayList<>();
        dfs(root, target, res, new ArrayList());
 
        return res;
    }
 
    public void dfs(TreeNode root, int target, ArrayList> res, ArrayList combine) {
        if (root == null) {
            return;
        }
 
        combine.add(root.val);
        if (root.left == null && root.right == null && root.val == target) {
            res.add(new ArrayList<>(combine));
        }
 
        dfs(root.left, target - root.val, res, combine);
        dfs(root.right, target - root.val, res, combine);
        combine.remove(combine.size() - 1);
 
        return;
    }
}

总结

利用递归，深度优先遍历二叉树，当遍历到叶结点时，判断当前路径和是否等于指定数字，若是则将该路径添加进最终需要返回的结果中。这里需要注意，应该使用的是 res.add(new ArrayList<>(combine)) 而不是 res.add(combine) ，否则结果中的各个路径会随 combine 的增删变化。