登录
  • #刷题
  • #leetcode

339. Nested List Weight Sum 递归的base case是什么

akdhfikbk
379
1
大家好,这道题不好debug,因为好多写好的api

有一件事不明,就是如果输入是[[1,1],2,[​ ]]的时候,这个递归的程序怎样处理空list的?返回的是null吗?

进而,这个recursion的base case是什么? 貌似不像是树那样if(root==null) return 逻辑:

[mw_shl_code=java,true]/**

* // This is the interface that allows for creating nested lists.

* // You should not implement it, or speculate about its implementation



* public interface NestedInteger {

* // Constructor initializes an empty nested list.

* public NestedInteger();

*

* // Constructor initializes a single integer.

* public NestedInteger(int value);

*

* // @return true if this NestedInteger holds a single integer, rather than a nested list.

* public boolean isInteger();

*

* // @return the single integer that this NestedInteger holds, if it holds a single integer

* // Return null if this NestedInteger holds a nested list

* public Integer getInteger();

*

* // Set this NestedInteger to hold a single integer.

* public void setInteger(int value);

*

* // Set this NestedInteger to hold a nested list and adds a nested integer to it.

* public void add(NestedInteger ni);

*

* // @return the nested list that this NestedInteger holds, if it holds a nested list

* // Return null if this NestedInteger holds a single integer

* public List<NestedInteger> getList();

* }

*/

class Solution {

public int depthSum(List<NestedInteger> nestedList) {

if(nestedList == null) return 0;

return helper(nestedList,1);

}

public int helper(List<NestedInteger> nestedList, int level){

int sum=0;

for(NestedInteger nest: nestedList){

if(nest.isInteger()){

sum+=nest.getInteger() * level;

}else{

sum+= helper(nest.getList(),level+1);//所以这个recursion没有base case吗

}

}

return sum;

}

}[/mw_shl_code]

求教,谢谢
1条回复
热度排序

发表回复