NestedInteger 类

Previous路径与路径和 Next(FB) 从 Binary Tree Path 看如何递归转迭代

Last updated 4 years ago

Was this helpful?

NestedInteger 类

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

这树，长这样：

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

    public List<Integer> flatten(List<NestedInteger> nestedList) {
        // Write your code here
        List<Integer> rst = new ArrayList<>();
        for(NestedInteger node : nestedList){
            dfs(rst, node);
        }
        return rst;
    }

    private void dfs(List<Integer> rst, NestedInteger node){
        if(node.isInteger()){
            rst.add(node.getInteger());
        } else {
            for(NestedInteger next : node.getList()){
                dfs(rst, next);
            }
        }
    }

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

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

    public List<Integer> flatten(List<NestedInteger> nestedList) {
        // Write your code here
        List<Integer> rst = new ArrayList<>();
        Stack<NestedInteger> stack = new Stack<>();

        for(int i = nestedList.size() - 1; i >= 0; i--){
            stack.push(nestedList.get(i));
        }

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

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

public class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        int sum = 0;
        for(NestedInteger num : nestedList){
            sum += dfs(num, 1);
        }
        return sum;
    }

    private int dfs(NestedInteger nestedInt, int depth){
        if(nestedInt.isInteger()){
            return depth * nestedInt.getInteger();
        } else {
            int sum = 0;
            List<NestedInteger> list = nestedInt.getList();
            for(NestedInteger num : list){
                sum += dfs(num, depth + 1);
            }
            return sum;
        }
    }
}

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

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

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

这题的正确理解是，每当看到 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;

居然能一次 AC ，好神奇。。

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;
    }
}

这题和 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 中。

速度超过 80.50% ，下面的代码能 AC

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

public class NestedIterator implements Iterator<Integer> {
    Stack<Iterator<NestedInteger>> stack;
    Iterator<NestedInteger> cur;
    Integer next;

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

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

    @Override
    public boolean hasNext() {
        while(cur.hasNext() || !stack.isEmpty()){
            while(cur.hasNext()){
                NestedInteger elem = cur.next();
                if(elem.isInteger()) {
                    next = elem.getInteger();
                    return true;
                } else {
                    if(cur.hasNext()) stack.push(cur);
                    cur = elem.getList().iterator();
                }
            }
            if(!stack.isEmpty()) cur = 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);
    }
}

中间的部分改成迭代也很简单，这样就行；

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

Previous路径与路径和 Next(FB) 从 Binary Tree Path 看如何递归转迭代

Last updated 4 years ago

Was this helpful?