Nested Integer

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

这树，长这样：

所以NestedInteger问题，和之前的路径问题有些相似之处，都可以用DFS递归实现。就是在细节上要注意NestedInteger本身的方法。对于里面的元素要用树的节点的模式来思考。

Flatten List

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

NestedInteger的三个方法挺有意思的。

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> result = new ArrayList<>();
        for (NestedInteger node : nestedList) {
            dfs(node, result);
        }
        return result;
    }
    private void dfs(NestedInteger node, List<Integer> result) {
        if (node.isInteger()) {
            result.add(node.getInteger());
        } else {
            for (NestedInteger next : node.getList()) {
                dfs(next, result);
            }
        }
    }
}

迭代先试了下 BFS ，发现顺序有问题。靠 Stack 遇到 List 就反向遍历 push 倒是能跑通。

这个迭代写法其实就是自己用 Stack 复现了一遍递归的过程。

public class Solution {
    public List<Integer> flatten(List<NestedInteger> nestedList) {
        List<Integer> result = new ArrayList<>();
        Stack<NestedInteger> stack = new Stack<>();

        for (int i = nestedList.size() - 1; i >= 0; --i) {
            stack.push(nestedList.get(i));
        }
        while (!stack.isEmpty()) {
            if (stack.peek().isInteger()) {
                result.add(stack.pop().getInteger());
            } else {
                List<NestedInteger> list = stack.pop().getList();
                for (int i = list.size() - 1; i >= 0; --i) {
                    stack.push(list.get(i));
                }
            }
        }
        return result;
    }
}

339. Nested List Weight Sum

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

364. Nested List Weight Sum II

和上一题反过来。

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

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

感觉还是很巧妙的

public class Solution {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        int prevAll = 0;
        int total = 0;
        while (!nestedList.isEmpty()) {
            List<NestedInteger> nextList = new ArrayList<>();
            for (NestedInteger node : nestedList) {
                if (node.isInteger()) {
                    prevAll += node.getInteger();
                } else {
                    nextList.addAll(node.getList());
                }
            }
            total += prevAll;
            nestedList = nextList;
        }
        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;
    }
}

341. 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 中。

下面的代码能 AC，但是我觉得不算很严谨，如果测试用例调用很多次 hasNext()，会对现有的 iterator 造成影响，不应该是正确的。

public class NestedIterator implements Iterator<Integer> {

    Stack<Iterator<NestedInteger>> stack;
    Iterator<NestedInteger> curt;
    Integer next;

    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<>();
        curt = nestedList.iterator();
        next = null;
    }

    @Override
    public Integer next() {
        return next;
    }

    @Override
    public boolean hasNext() {
        while (curt.hasNext() || !stack.isEmpty()) {
            while (curt.hasNext()) {
                NestedInteger elem = curt.next();
                if (elem.isInteger()) {
                    next = elem.getInteger();
                    return true;
                } else {
                    if (curt.hasNext()) stack.push(curt);
                    curt = elem.getList().iterator();
                }
            }
            if (!stack.isEmpty()) curt = stack.pop();
        }
        return false;
    }
}

我比较认同的写法是这种，用内部函数来准备 next() 和 hasNext() API 的返回。

public class NestedIterator implements Iterator<Integer> {

    Stack<Iterator<NestedInteger>> stack;
    Iterator<NestedInteger> cur;
    Integer num;

    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<>();
        cur = nestedList.iterator();
        num = internalNext();
    }

    private Integer internalNext(){
        if(cur.hasNext()){
            NestedInteger elem = cur.next();
            if(elem.isInteger()){
                return elem.getInteger();
            } else {
                if(cur.hasNext()) stack.push(cur);
                cur = elem.getList().iterator();
                return internalNext();
            }
        } else {
            if(stack.isEmpty()) return null;
            cur = stack.pop();
            return internalNext();
        }
    }

    @Override
    public Integer next() {
        Integer tmp = num;
        num = internalNext();
        return tmp;
    }

    @Override
    public boolean hasNext() {
        return (num != null);
    }
}

385. Mini Parser

非常不错的一道题。

递归思路是，首先判断s是否为空，为空直接返回，

不为空的话看首字符是否为'['，不是的话说明s为一个整数，我们直接返回结果。

如果首字符是'['，且s长度小于等于2，说明没有内容，直接返回结果。

反之如果s长度大于2，我们从i = 1开始遍历，我们需要一个变量start来记录某一层的起始位置，用count来记录跟其实位置是否为同一深度，count=0表示同一深度

由于中间每段都是由逗号隔开，所以当我们判断当count为0，且当前字符是逗号或者已经到字符串末尾了，把start到当前位置之间的字符串取出来递归调用函数，把返回结果加入res中，然后start更新为i+1。

如果遇到'['，count自增1，若遇到']'，count自减1。

字符串转数字的时候考虑负数的处理。

public class Solution {
    public NestedInteger deserialize(String s) {
        if (s == null || s.length() == 0) return new NestedInteger();
        if (s.charAt(0) != '[') return new NestedInteger(convert(s));
        if (s.length() <= 2) return new NestedInteger();

        NestedInteger result = new NestedInteger();
        int start = 1;
        int count = 0;
        for (int i = 1; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (count == 0 && (ch == ',' || i == s.length() - 1)) {
                result.add(deserialize(s.substring(start, i)));
                start = i + 1;
            } else if (ch == '[') {
                count++;
            } else if (ch == ']') count--;
        }
        return result;
    }
    private int convert(String s) {
        if (s == null || s.length() == 0) return 0;
        int total = 0;
        int start = 0;
        int flag = 1;
        if (s.charAt(0) == '-'){
            flag = -1;
            start++;
        }
        for (int i = start; i < s.length(); ++i) {
            char ch = s.charAt(i);
            total = total * 10 + (ch - '0');
        }
        return total * flag;
    }
}