Leetcode exercise - 113 Path sum II

1. Title Description

113. The sum of the paths II
Give you the root node of the binary tree root And an integer target and targetSum , Find out all From the root node to the leaf node The path sum is equal to the given target sum .

Leaf node A node without children .

Example 1：

 Input ：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 Output ：[[5,4,11,2],[5,8,4,5]]

Example 2：

 Input ：root = [1,2,3], targetSum = 5
 Output ：[]

Example 3：

 Input ：root = [1,2], targetSum = 0
 Output ：[]

2. Problem solving ideas and codes

2.1 Their thinking

This problem is to find the path from the root node to the upper sum of the leaf node as the target , You can use preorder traversal for processing . When the node is not a leaf node , Put the current node into the path list , And the target value minus the current node value ; If the current node is a leaf node , You need to judge target Is it 0, If it is 0, Then put the current path into the result list ; If not 0, Then return to . After processing the left and right nodes, you need to delete the current node from the path list . Take the topic as an example 1 As an example ：

First, traverse the binary tree downward from the root node , Put the current node into the path list , meanwhile target Subtract the current node value .

When traversing the leaf node , Judge target Is it 0, Not at this time 0, Therefore, this path does not meet the requirements , Return to the previous node .

When returning, you need to remove the current node from the path list , Then continue down to 2 This node . here target be equal to 0, Meet the requirements , take [5, 4, 11, 2] This path is put into the result . Repeat the above steps and continue to traverse until the end .

2.2 Code

class Solution {
    
    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
    
        if (root == null) {
    
            return ans;
        }
        process(root, new ArrayList<>(), target);
        return ans;
    }

    public void process(TreeNode root, List<Integer> tmp, int target) {
    
        if (root == null) {
    
            return;
        }
        tmp.add(root.val);
        target -= root.val;
        if (root.left == null && root.right == null && target == 0){
    
            //  If the current node is a leaf node , also  target  be equal to  0, Put the path into the result list 
            ans.add(new ArrayList<>(tmp));
        }
        process(root.left, tmp, target);
        process(root.right, tmp, target);
        //  After processing the left and right nodes, remove the current node from the path list 
        tmp.remove(tmp.size() - 1);
    }
}

2.3 test result

Pass the test

3. summary

• Use preorder traversal to solve
• Each node needs to move the current node out of the path list after processing the left and right nodes