339. Nested List Weight Sum

Easy (LinkedIn)

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1: Given the list [[1,1],2,[1,1]], return 10. (four 1's at depth 2, one 2 at depth 1)

Example 2: Given the list [1,[4,[6]]], return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 42 + 63 = 27)

Solution 1: recursion

public class Solution {

private int sum = 0;

public int depthSum(List<NestedInteger> nestedList) {
    if(nestedList == null || nestedList.size() == 0) {
        return 0;
    }

    for(NestedInteger node : nestedList) {
        DFS(node, 1);
    }

    return sum;
}

public void DFS(NestedInteger node, int level) {
    if(node.isInteger() == true) {
        sum += node.getInteger() * level;
        return ;
    }

    for(NestedInteger next : node.getList()) {
        DFS(next, level + 1);
    }
}

}

Solution 2: iterator

public class Solution {

public int depthSum(List<NestedInteger> nestedList) {
    if(nestedList == null || nestedList.size() == 0) {
        return 0;
    }

    Stack<Node> stack = new Stack<>();
    int sum = 0;

    for(NestedInteger node : nestedList) {
        if(node.isInteger() == true) {
            sum += node.getInteger();
        } else {
            stack.push(new Node(node, 1));
        }
    }

    while(!stack.isEmpty()) {
        Node n = stack.pop();
        NestedInteger current = n.node;
        int curLevel = n.level + 1;

        for(NestedInteger next : current.getList()) {
            if(next.isInteger()) {
                sum += next.getInteger() * curLevel;
            } else {
                stack.push(new Node(next, curLevel));
            }
        }
    }

    return sum;
}

class Node {
    NestedInteger node;
    int level;

    public Node(NestedInteger node, int level) {
        this.node = node;
        this.level = level;
    }
}

}

364. Nested List Weight Sum II

Medium (LinkedIn)

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:

Given the list [[1,1],2,[1,1]], return 8. (four 1's at depth 1, one 2 at depth 2)

Example 2:

Given the list [1,[4,[6]]], return 17. (one 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 13 + 42 + 6*1 = 17)

Solution 1: iterator

Explaination:

1. Using stack to store the element which is not a integer.
2. Using list to store the element which is a integer.
3. Using a variable totalLevel to keep the total level.

public class Solution {

public int depthSumInverse(List<NestedInteger> nestedList) {
    if(nestedList == null || nestedList.size() == 0) {
        return 0;
    }

    int sum = 0;
    int totalLevel = 1;
    Stack<Node> stack = new Stack<>();
    List<Node> list = new ArrayList<>();

    for(NestedInteger node : nestedList) {
        if(node.isInteger() == true) {
            list.add(new Node(node, 1));
        } else {
            stack.push(new Node(node, 1));
        }
    }

    while(!stack.isEmpty()) {
        Node n = stack.pop();
        NestedInteger current = n.node;
        int curLevel = n.level + 1;
        totalLevel = Math.max(totalLevel, curLevel);

        for(NestedInteger next : current.getList()) {
            if(next.isInteger() == true) {
                list.add(new Node(next, curLevel));
            } else {
                stack.push(new Node(next, curLevel));
            }
        }
    }

    for(Node n : list) {
        sum += n.node.getInteger() * (totalLevel - n.level + 1);
    }

    return sum;
}

class Node {
    NestedInteger node;
    int level;

    public Node(NestedInteger node, int level) {
        this.node = node;
        this.level = level;
    }
}

}

Solution 2: recursion

public class Solution {

private Stack<Node2> stack = new Stack<Node2>();
private int totalLevel = 0;

public int depthSumInverse2(List<NestedInteger> nestedList) {
    if(nestedList == null || nestedList.size() == 0){
        return 0;
    }

    int ans = 0;

    for(NestedInteger item : nestedList){
        dfs(item, 1);    // 必须从1开始 ！！！
    }

    while(!stack.isEmpty()){
        Node2 tempNode = stack.pop();
        ans += tempNode.value * (totalLevel - tempNode.level + 1);
    }

    return ans;
}

public void dfs(NestedInteger node, int level){
    totalLevel = Math.max(totalLevel, level);

    if(node.isInteger() == true){
        stack.push(new Node2(node.getInteger(), level));
    } else {
        List<NestedInteger> list = node.getList();
        for(NestedInteger nextNode : list){
            dfs(nextNode, level + 1);
        }
    }
}

class Node2{
    int value;
    int level;

    public Node2(int v, int l){
        value = v;
        level = l;
    }
}

}