Paths in a Binary Tree With a Given Sum

1. Problem Description

Given the root node of a binary tree and an integer, print all paths in the binary tree whose node values sum to the given integer. A path is defined as the nodes traversed from the root node of the tree downward to a leaf node. (Note: in the returned list, arrays with greater length come first.)

2. Approach

• Depth-first traversal = preorder traversal + backtracking

3. Implementation

• java

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

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target)
    {
        // Check parameters
        if (root == null)
        {
            return res;
        }
        // Preorder traversal
        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
        {
            // Save the path when a leaf node is reached (both left and right children are empty)
            if (root.right == null)
            {
                res.add(new ArrayList<>(list));
            }
        }


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

        // Backtrack
        list.removeLast();
    }
}

• go

// Time complexity: O(n), all nodes in the tree need to be traversed once
// Space complexity: O(n), when the tree degenerates into a linked list, the recursion space is 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) {
	// Preorder traversal
	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)

	// Backtrack after processing
	*path = (*path)[:len(*path)-1]
}

4. References

• Path in a Binary Tree with a Given Sum - NowCoder
• Path Sum - LeetCode