二叉树中和为某一值的路径

1. 题目描述

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

2. 思路

• 深度优先遍历=先序遍历+回溯

3. 实现

• java

public class 二叉树中和为某一值的路径
{
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target)
    {
        //检查参数
        if (root == null)
        {
            return res;
        }
        //先序遍历
        LinkedList<Integer> list = new LinkedList<>();
        this.preOrder(root,list);

        return res.stream().filter(path -> path.stream().mapToInt(a -> a).sum() == target).collect(Collectors.toCollection(ArrayList::new));
    }

    private void preOrder(TreeNode root, LinkedList<Integer> list)
    {
        list.add(root.val);

        if (root.left != null)
        {
            this.preOrder(root.left, list);
        }
        else
        {
            //到达叶子节点（左右节点为空）的时候保存该路径
            if (root.right == null)
            {
                res.add(new ArrayList<>(list));
            }
        }


        if (root.right != null)
        {
            this.preOrder(root.right,list);
        }

        //回退
        list.removeLast();
    }
}

• go

//时间复杂度：O(n), 树的所有节点需要遍历一次
//空间复杂度：O(n), 当树退化到链表时，递归空间为O(n)
func FindPath(root *TreeNode, expectNumber int) [][]int {
	allPaths := make([][]int, 0)
	path := make([]int, 0)
	res := make([][]int, 0)
	findPath(root, &allPaths, &path)
	for _, p := range allPaths {
		s := sum(p...)
		if s == expectNumber {
			res = append(res, p)
		}
	}

	return res
}

func sum(data ...int) int {
	sum := 0
	for _, d := range data {
		sum += d
	}
	return sum
}

func findPath(root *TreeNode, allPaths *[][]int, path *[]int) {
	//先序遍历
	if root == nil {
		return
	}
	*path = append(*path, root.Val)
	if root.Left == nil && root.Right == nil {
		tmp := make([]int, len(*path))
		copy(tmp, *path)
		*allPaths = append(*allPaths, tmp)
	}
	findPath(root.Left, allPaths, path)
	findPath(root.Right, allPaths, path)

	//处理完后回退
	*path = (*path)[:len(*path)-1]
}

4. 参考

• 二叉树中和为某一值的路径_牛客网
• Path Sum - LeetCode