Java DFS: easy to follow algorithm


  • 0
    A

    Basic idea is to recursively check each node and use it as the starting 'value' to add with its leftChild's all possible pathSums and rightChild's all possible pathSums

    public int pathSum(TreeNode root, int sum) {
        // algorithm: simply calcualte all possible pathSums 
        if (null == root) {
            return 0;
        }
        PathSumHelper helper = pathSums(root, sum);
        return helper.countOfMatchingPathSums;
    }
    
    private PathSumHelper pathSums(TreeNode root, int target) {
        assert null != root;
        // we always need to check the root node itself: value, and add it pathSum list
        PathSumHelper helper = new PathSumHelper();
        helper.listPathSums = new ArrayList<>();
        if (target == root.val) {
            helper.countOfMatchingPathSums = 1;
        }
        helper.listPathSums.add(root.val);
    
        if (null == root.left && null == root.right) {
            return helper;
        }
        if (null != root.left) {
            PathSumHelper helperLeftChild = pathSums(root.left, target);
            helper.countOfMatchingPathSums += helperLeftChild.countOfMatchingPathSums;
            
            for (int pathSum : helperLeftChild.listPathSums) {
                if (target == root.val + pathSum) {
                    helper.countOfMatchingPathSums += 1;
                }
                int newPathSum = root.val + pathSum;
                helper.listPathSums.add(newPathSum);
            }
        }
        if (null != root.right) {
            PathSumHelper helperRightChild = pathSums(root.right, target);
            helper.countOfMatchingPathSums += helperRightChild.countOfMatchingPathSums;
            
            for (int pathSum : helperRightChild.listPathSums) {
                if (target == root.val + pathSum) {
                    helper.countOfMatchingPathSums += 1;
                }
                int newPathSum = root.val + pathSum;
                helper.listPathSums.add(newPathSum);
            }
        }
        return helper;
    }
    
    private class PathSumHelper {
        List<Integer> listPathSums;
        int countOfMatchingPathSums;
    }

Log in to reply
 

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