Java DFS solution, customized Pair class


  • 0
    B

    Java DFS solution, using DFS to get the maximum depth, using a self-defined class Pair to represent integer and its depth, store all (integer, depth) pair in a list and add them together.

    public class Solution {
        public class Pair {
            int key;
            int depth;
            public Pair (int x, int y) {
                this.key = x;
                this.depth = y;
            }
        }
        
        int maxDepth = 0;
        List<Pair> myList = new ArrayList<>();
        
        public int depthSumInverse (List<NestedInteger> nestedList) {
            if (nestedList == null) {
                return 0;
            }
    
            dfs(nestedList, 1);
            int res = 0;
            for (Pair ele : this.myList) {
                res += (this.maxDepth - ele.depth + 1) * ele.key;
            }
    
            return res;
        }
    
        public void dfs (List<NestedInteger> nestedList, int depth) {
            this.maxDepth = Math.max(this.maxDepth, depth);
            for (NestedInteger ele : nestedList) {
                if (ele.isInteger()) {
                    this.myList.add(new Pair(ele.getInteger(), depth));
                } else {
                    dfs(ele.getList(), depth + 1);
                }
            }
        }
    }
    

Log in to reply
 

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