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