BFS Solution in JAVA


  • 0
    M

    There are many DFS or Array solutions. Here is my BFS sulution:

    class Solution {
        public int pathSum(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            int res = 0;
            Queue<Integer> queue = new LinkedList<>();
            Queue<Integer> sum = new LinkedList<>();
            queue.offer(nums[0]);
            sum.offer(nums[0] % 10);
            int i = 1;
            while (!queue.isEmpty()) {
                int curr = queue.poll();    // the current node
                int cursum = sum.poll();   // the current node's sum (the sum from root to the current node)
                boolean hasChild = false;
                while (i < nums.length && nums[i] / 100 == (curr / 100 + 1) && (nums[i] / 10 % 10 + 1) / 2 == curr / 10 % 10) {     // to check whether nums[i] is the current node's child
                    hasChild = true;
                    queue.offer(nums[i]);
                    sum.offer(cursum + nums[i] % 10);
                    i++;
                }
                if (!hasChild) res += cursum;   // if the current node has no children, add the current sum into the result. 
            }
            return res;
        }
    }
    

Log in to reply
 

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