Simple DFS Java Solution


  • 21
    X

    Save intermediate result into stack and save the stack into result array once its sum == required sum.

    public class Solution {
        private List<List<Integer>> resultList = new ArrayList<List<Integer>>();
        
        public void pathSumInner(TreeNode root, int sum, Stack<Integer>path) {
            path.push(root.val);
            if(root.left == null && root.right == null)
                if(sum == root.val) resultList.add(new ArrayList<Integer>(path));
            if(root.left!=null) pathSumInner(root.left, sum-root.val, path);
            if(root.right!=null)pathSumInner(root.right, sum-root.val, path);
            path.pop();
        }
        
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            if(root==null) return resultList;
            Stack<Integer> path = new Stack<Integer>();
            pathSumInner(root, sum, path);
            return resultList;
        }
    }

  • 8

    +1 :)

    Honestly, I liked this solution and this is how even I could think of when I saw the problem.

    Changing your code a little bit to use ArrayList, also making resultList as local.

    public void pathSumInner(TreeNode root, int sum, List<Integer>path, List<List<Integer>> result) {
        path.add(root.val);
        if(root.left == null && root.right == null)
            if(sum == root.val) result.add(new ArrayList<Integer>(path));
        if(root.left!=null) pathSumInner(root.left, sum-root.val, path, result);
        if(root.right!=null)pathSumInner(root.right, sum-root.val, path, result);
        path.remove(path.size()-1);
    }
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();
        if(root==null) return resultList;
        List<Integer> currentPath = new ArrayList<Integer>();
        pathSumInner(root, sum, currentPath, resultList);
        return resultList;
    }

  • 0
    G
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 0
    C

    @xuhua.alex What is the time complexity?


  • 0
    A

    @jaqenhgar Hi, Can I ask what's the usage for path.remove(path.size()-1) for? Thanks in advance


  • 0

    @arthursunbao I'm using an array list, so it's equivalent of popping the last added element in stack like OP solution.


  • 0
    W

    Some idea. Here is my python code

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def pathSum(self, root, sum):
            """
            :type root: TreeNode
            :type sum: int
            :rtype: List[List[int]]
            """
            self.res = []
    
            if not root:
                return self.res
            
            
            def dfs(root, sum, stack):
                stack.append(root.val)
                if not root.left and not root.right and sum == root.val:
                    self.res.append(stack[:])
                if root.left:
                    dfs(root.left, sum-root.val, stack)
                if root.right:
                    dfs(root.right, sum-root.val, stack)
                stack.pop()
            
            dfs(root, sum, [])
            
            return self.res
    

  • 0
    W

    @jaqenhgar
    I'm confused about popping the last added element, why should we do this? can you explain it please? thanks


  • 0
    B

    @weiyang__ said in Simple DFS Java Solution:

    @jaqenhgar
    I'm confused about popping the last added element, why should we do this? can you explain it please? thanks

    @arthursunbao said in Simple DFS Java Solution:

    @jaqenhgar Hi, Can I ask what's the usage for path.remove(path.size()-1) for? Thanks in advance

    Hi guys
    So I just checked the program. Basically, it means after reaching to one of the leaf nodes. The program needs to go up one level to check the other side of the tree. Thus we need to remove it from the current path as this node is not on the current path any more. Also, it needs to be executed for both left and right subtree.

    I hope it helps.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.