非死不可 店面

一轮 国人哥哥

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

二轮 三姐

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

希望三姐能给过啊。。。去年挂在二面 今年再挂在二面 就要哭死了发个帖子 攒个人品。。
新来的 才开始找工作 求大米~~

我说一个leaf to root的思路，就是从下往上返回一个List<StringBuilder>, 每个root都把左右子节点返回的Stringbuilder append当前root。代码如下：

1.         public List<String> leafToRootPath(TreeNode root){
   
2.                 // get a list of StringBuilder
   
3.                 List<StringBuilder> sbs = pathHelper(root);               
   
4.                 List<String> res = new ArrayList<>(sbs.size());
   
5.                
   
6.                 // transfer to String
   
7.                 for(StringBuilder sb : sbs){
   
8.                         res.add(sb.toString());
   
9.                 }
   
10.                
    
11.                 return res;
    
12.         }
    
13. 
    
14.         private List<StringBuilder> pathHelper(TreeNode root) {
    
15.                 // return nothing
    
16.                 if(root == null) return new ArrayList<>();
    
17.                
    
18.                 // leaf node
    
19.                 if(root.left == null && root.right == null){
    
20.                         List<StringBuilder> res = new ArrayList<>();
    
21.                         res.add(new StringBuilder().append(root.key));
    
22.                         return res;
    
23.                 }
    
24.                
    
25.                 // get path from left and right
    
26.                 List<StringBuilder> left = pathHelper(root.left);
    
27.                 List<StringBuilder> right = pathHelper(root.right);
    
28.                 // merge path from two subtree
    
29.                 left.addAll(right);
    
30.                 // add current node to path
    
31.                 for(StringBuilder sb : left){
    
32.                         sb.append(root.key);
    
33.                 }
    
34.                
    
35.                 return left;
    
36.         }

复制代码

时间复杂度是O(n)每个点被遍历visit两边，往下一遍，往上一遍。空间复杂度不考虑答案本身最坏的空间是O(n), used by call stack.
这道题我觉得不可能做到小于O(n)的，因为path的问题规模已经是Ω(n)了。除非他问的不是path本身是什么，而是path有多少个。

DylanZhang 发表于 2018-11-9 08:53
我说一个leaf to root的思路，就是从下往上返回一个List, 每个root都把左右子节点返回的Stringbuilder appe ...

请问时间复杂度是多少？log n 或 h吗？

楼主蠢了 不会加 隐藏内容、、

LZ加油，希望你能拿到昂赛

print是什么顺序？从最底层开始按层print？

pandami 发表于 2018-11-9 06:27
print是什么顺序？从最底层开始按层print？

从leat到root的顺序 打印

leaf to root正确的思路应该是什么啊，用map映射child parent 关系，然后碰到leaf就遍历map一直print找到root？

leaf 到 root 用 buttom up ?
然后 stringbuilder reverse的complexity是O(n) 如果加在一起的话 是O(n^2) ?