LeetCode - Medium - 113. Path Sum II-蒲公英云

LeetCode - Medium - 113. Path Sum II

Topic

Tree
Depth-first Search

Description

https://leetcode.com/problems/path-sum-ii/

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path’s sum equals targetSum.

A leaf is a node with no 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: []

Constraints:

The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

Analysis

方法一：递归法

方法二：迭代法

Submission

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import com.lun.util.BinaryTree.TreeNode;
public class PathSumII { 
    //方法一：递归法
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) { 
        List<List<Integer>> result = new ArrayList<>();
        pathSum(root, 0, targetSum, new ArrayList<>(), result);
        return result;
    }
    private void pathSum(TreeNode node, int sum, int targetSum, List<Integer> path, List<List<Integer>> result) { 
        if(node == null) return;
        path.add(node.val);
        sum += node.val;
        if(node.left == null && node.right == null && sum == targetSum)
            result.add(new ArrayList<>(path));
        pathSum(node.left, sum, targetSum, path, result);
        pathSum(node.right, sum, targetSum, path, result);
        path.remove(path.size() - 1);
    }
    //方法二：迭代法
    @SuppressWarnings("unchecked")
    public List<List<Integer>> pathSum2(TreeNode root, int targetSum) { 
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) return result;
        LinkedList<Object[]> stack = new LinkedList<>();
        stack.push(new Object[] { root, 0, new ArrayList<>()});
        while(!stack.isEmpty()) { 
            Object[] arr = stack.pop();
            TreeNode node = (TreeNode)arr[0];
            int sum = (int)arr[1];
            List<Integer> path = (List<Integer>)arr[2];
            path.add(node.val);
            sum += node.val;
            if(node.left == null && node.right == null) { 
                if(sum == targetSum) 
                    result.add(path);
            }else if(node.left != null && node.right == null) { 
                stack.push(new Object[] { node.left, sum, path});
            }else if(node.left == null && node.right != null) { 
                stack.push(new Object[] { node.right, sum, path});
            }else { 
                stack.push(new Object[] { node.right, sum, new ArrayList<>(path)});
                stack.push(new Object[] { node.left, sum, path});
            }
        }
        return result;
    }
}

Test

import static org.junit.Assert.*;
import java.util.Arrays;
import org.hamcrest.collection.IsEmptyCollection;
import org.hamcrest.collection.IsIterableContainingInAnyOrder;
import org.junit.Test;
import com.lun.util.BinaryTree;
import com.lun.util.BinaryTree.TreeNode;
public class PathSumIITest { 
    @SuppressWarnings("unchecked")
    @Test
    public void test() { 
        PathSumII obj = new PathSumII();
        TreeNode root1 = BinaryTree.integers2BinaryTree(5,4,8,11,null,13,4,7,2,null,null,5,1);
        assertThat(obj.pathSum(root1, 22), //
                IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(5,4,11,2), Arrays.asList(5,8,4,5)));
        TreeNode root2 = BinaryTree.integers2BinaryTree(1, 2, 3);
        assertThat(obj.pathSum(root2, 5), IsEmptyCollection.empty());
        TreeNode root3 = BinaryTree.integers2BinaryTree(1, 2);
        assertThat(obj.pathSum(root3, 0), IsEmptyCollection.empty());
    }
    @Test
    @SuppressWarnings("unchecked")
    public void test2() { 
        PathSumII obj = new PathSumII();
        TreeNode root1 = BinaryTree.integers2BinaryTree(5,4,8,11,null,13,4,7,2,null,null,5,1);
        assertThat(obj.pathSum2(root1, 22), //
                IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(5,4,11,2), Arrays.asList(5,8,4,5)));
        TreeNode root2 = BinaryTree.integers2BinaryTree(1, 2, 3);
        assertThat(obj.pathSum2(root2, 5), IsEmptyCollection.empty());
        TreeNode root3 = BinaryTree.integers2BinaryTree(1, 2);
        assertThat(obj.pathSum2(root3, 0), IsEmptyCollection.empty());
    }
}