NestedInteger 类

所有的 NestedInteger 问题，都是多叉树的问题。

这树，长这样：

(G)Flatten List

递归的很简单，对于每棵 tree root 都是一个【左 - 右】的顺序 dfs 处理其 subtrees.

public class Solution {

    // @param nestedList a list of NestedInteger
    // @return a list of integer
    public List<Integer> flatten(List<NestedInteger> nestedList) {
        // Write your code here
        List<Integer> list = new ArrayList<Integer>();
        for(NestedInteger x: nestedList){
            if(x.isInteger()){
                list.add(x.getInteger());
            }
            else{
                list.addAll(flatten(x.getList()));    
            }
        }
        return list;
    }
}

Nested List Weight Sum

就是最简单的 DFS，非常 trivial 的问题。。

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

Nested List Weight Sum II

从上往下递归可以传参数，自底向上递归传 tuple.

比较诡异的是 [[-1], [[-1]]] 这样的 test case ，第一个 [-1] 的 weight 居然是 2，导致最终结果是 -3 .. 让我觉得这题的 test case 定义有点不清楚。。

于是下面这个 dfs 的代码会出错，因为没正确处理当前 list 也是嵌套的正确 weight. 这段代码的思路是对于每一个位置，其 weight = 其子树的最深距离，但是和原题的定义不一样。

面试时讨论清楚怎么定义height

这题的正确理解是，每当看到 Integer，代表这是一个leaf node；每当看到一个 List，代表这是一个 subtree.

public class Solution {
    private class Tuple{
        int sum;
        int depth;
        public Tuple(int val, int dep){
            sum = val;
            depth = dep;
        }
    }
    public int depthSumInverse(List<NestedInteger> nestedList) {
        return dfs(nestedList).sum;
    }

    private Tuple dfs(List<NestedInteger> list){
        int sum = 0;
        int maxDepth = 1;
        for(NestedInteger node : list){
            if(!node.isInteger()){
                Tuple tuple = dfs(node.getList());
                sum += tuple.sum;
                maxDepth = Math.max(maxDepth, tuple.depth + 1);
            }
        }
        for(NestedInteger node : list){
            if(node.isInteger()) sum += maxDepth * node.getInteger();
        }

        return new Tuple(sum, maxDepth);
    }
}

于是乎这题的正确打开姿势其实是，自顶向下 level order 的看，只要下面还有一层，就把当前的所有结果都再加上一遍，起到相乘的效果；这样随着探索的不断深入，就可以正确地得到每层的正确 weight 了，因为每个 node 的 weight = 这个 node 到树最深节点的距离，一个天然的 BFS 问题。

public class Solution {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        int total = 0, prevAll = 0;
        while(!nestedList.isEmpty()){
            List<NestedInteger> nextLvl = new ArrayList<NestedInteger>();
            for(NestedInteger next : nestedList){
                if(next.isInteger()){
                    prevAll += next.getInteger();
                } else {
                    nextLvl.addAll(next.getList());
                }
            }

            total += prevAll;
            nestedList = nextLvl;
        }

        return total;
    }
}

这题当然也有 DFS 解法，要先把图过一遍，侦查好 maxDepth; 然后递归解决的时候，每一层的权重是 maxDepth - curDepth;+

public class Solution {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        int maxDepth = 0;
        for(NestedInteger next : nestedList){
            maxDepth = Math.max(getMaxDepth(next), maxDepth);
        }

        int sum = 0;
        for(NestedInteger next : nestedList){
            sum += dfs(next, maxDepth, 0);
        }

        return sum;
    }

    private int dfs(NestedInteger node, int maxDepth, int curDepth){
        if(node.isInteger()){
            return node.getInteger() * (maxDepth - curDepth);
        } else {
            int sum = 0;
            for(NestedInteger next : node.getList()){
                sum += dfs(next, maxDepth, curDepth + 1);
            }
            return sum;
        }
    }

    private int getMaxDepth(NestedInteger num){
        if(num.isInteger()) return 1;

        int max = 0;
        List<NestedInteger> nestedList = num.getList();
        for(NestedInteger next : nestedList){
            max = Math.max(getMaxDepth(next), max);
        }

        return max + 1;
    }
}

Flatten Nested List Iterator

这题和 BST iterator 很像，因为实际上都是利用 stack + cur 指针做一个 inorder 遍历。

不同之处是，Binary Tree 是双叉的，有个 node 就可以满足输出当前元素 + 寻找下一元素的需要，我们这个情况要复杂一些。+

NestedInteger 是一种树状结构，其中每一个是 List 的元素代表一个三角形，下面有自己的子树。

了解了这个结构之后，为了遍历寻找下一个元素，就需要依靠 List 作为一个 Collection interface 里自带的 iterator 了，在这里 iterator 就充当了 BST 里面 cur 指针的地位，用于在树上定位，和寻找下一个元素；同时 Stack<> 所存储的，就是各个 iterator.

实现过程中要注意的是，test case 会根据 boolean hasNext 决定是否继续输出，而这种结构不同于 binary tree，可能会有 [ [ ] ] 这种情况，此时 stack 里有东西，cur.hasNext() 也返回 true，无法正确得知下面是否真的有元素存在。+

所以要在 hasNext 里面执行程序逻辑。

同时对于一个 iterator，如果已经没有新元素了也不必要 push 到 stack 中。

犯错, stack.peek的时候没有check stack是否经是空了[[]], 将元素顺序压入栈的时候, [1,[4,[6]]] 输出为[6,4,1], 所以压入stack的时候要从list尾巴开始压入.

public class NestedIterator implements Iterator<Integer> {
    Stack<NestedInteger> stack;
    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<NestedInteger>();
        for(int i=nestedList.size()-1; i>=0;i--)
            stack.push(nestedList.get(i));
    }

    @Override
    public Integer next() {
        NestedInteger peek = stack.pop();
        return peek.getInteger();
    }

    @Override
    public boolean hasNext() {
        if(stack.isEmpty()) return false;
        NestedInteger peek = stack.peek();
        while(!stack.isEmpty()&&!peek.isInteger()){
            peek = stack.pop();
            List<NestedInteger> list = peek.getList();
            for(int i=list.size()-1; i>=0;i--)
                stack.push(list.get(i));
            if(stack.isEmpty()) return false;
            peek = stack.peek();
        }
        return !stack.isEmpty();
    }
}

hasnext()更好的写法

    @Override
    public boolean hasNext() {
        while(!stack.isEmpty()){ //in case [[][[]];
            if(stack.peek().isInteger())
                return true;
            List<NestedInteger> nestedList  = stack.pop().getList();
            for(int i=nestedList.size()-1;i>=0;i--)
                stack.push(nestedList.get(i));
        }
        return false;
    }

Nested Integer类