Java Solution DFS and BFS


  • 0
    H

    We may use DFS or BFS. DFS is preferable in case of a very wide tree.

    BFS

    public class Solution {
        public int depthSum(List<NestedInteger> nestedList) {
            int sum = 0, depth = 1;
            Deque<NestedInteger> queue = new LinkedList<>();
            queue.addAll(nestedList);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    NestedInteger num = queue.poll();
                    if (num.isInteger()) {
                        sum += num.getInteger() * depth;
                    } else {
                        for (NestedInteger sub : num.getList()) {
                            queue.offer(sub);
                        }
                    }
                }
                depth++;
            }
            return sum;
        }
    }
    

    DFS

    public class Solution {
        public int depthSum(List<NestedInteger> nestedList) {
            return helper(nestedList, 1);
        }
        private int helper(List<NestedInteger> nestedList, int depth) {
            int sum = 0;
            if (nestedList == null || nestedList.size() == 0) {
                return 0;
            }
            for (NestedInteger num : nestedList) {
                if (num.isInteger()) {
                    sum += num.getInteger() * depth;
                } else {
                    sum += helper(num.getList(), depth + 1);
                }
            }
            return sum;
        }
    }
    

Log in to reply
 

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