113. Total path II

problem
Given a binary tree and a target sum, find all paths from the root node to the leaf node whose total path is equal to the given target sum.
Example

thinking
Method (root, changing sum, 2D array res, path list)

  • Method 1
    How to save the path from root node to leaf node? The get() method needs to have the array list, because it needs to get (left subtree) and get (right subtree) successively, so the two arrays can't be involved. If get (left subtree) modifies the list, it will directly affect the list passed in get (right subtree)
    So: for a node, copy a list when get (left subtree) and a list when get (right subtree)
  • Method 2: too many new arrays are created in method 1, only the required paths are copied.
    Use li to save the value (path) of the accessed node. After accessing the node:
    If it is exactly a leaf node and its value is exactly sum, copy li and add the two-dimensional array res
    Otherwise, access the left and right subtrees
    Finally, pop the value out of li
    Code
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//Method 1
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        if(root==null) return res;
        
        get(root,sum,res,list);
        return res;
    }
    public void get(TreeNode root, int sum, List<List<Integer>> res, List<Integer> list) {
        if (root==null) return ;
        list.add(root.val);
        if (root.left==null && root.right==null && root.val==sum) {
            
            res.add(list);
            return;
        }
        
        sum-=root.val;
        get(root.left, sum, res, new ArrayList<Integer>(list));
        get(root.right, sum, res, new ArrayList<Integer>(list));

        
    }
}
//Method 2
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        get(root, sum, res, list);
        return res;
    }
    public void get(TreeNode root, int sum, List<List<Integer>> res, List<Integer> list) {
        if (root == null) return ;
        list.add(root.val);
        if (root.left==null && root.right==null && root.val==sum)
        {
            res.add(new ArrayList<Integer>(list));
            //return; this element has not been popped yet
        }else {
            sum-=root.val;
            get(root.left,sum,res,list);
            get(root.right,sum,res,list);
        }
       
        list.remove(list.size()-1);
    }
}
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# Method 1
class Solution:
    
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res=list()
        li=list()
        if root is None: return res
        self.get(root,sum,res,li)
        return res
    def get(self,root,sum,res,li):
        if root is None: return None
        li.append(root.val)
        if root.left is None and root.right is None and sum==root.val:
            res.append(li)
            return None
        sum-=root.val
        self.get(root.left,sum,res,copy.copy(li)) 
        self.get(root.right,sum,res,copy.copy(li))
#Method 2
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res=list()
        li=list()
        
        if root is None: return res
        self.get(root,sum,res,li)
        return res
    def get(self, root, sum, res, li):
        if root is None: return None
        li.append(root.val)
        if root.left is None and root.right is None and root.val==sum:
            res.append(copy.copy(li))
            #return None may be over, because it hasn't been returned yet
        else:
            sum-=root.val
            self.get(root.left,sum,res,li)
            self.get(root.right,sum,res,li)
        
        li.pop()
78 original articles published, 7 praised, 10000 visitors+
Private letter follow

Posted on Thu, 30 Jan 2020 06:23:37 -0800 by billy2shoe