Populating Next Right Pointers in Each Node

给了一个完美的二叉树, 填充其next节点

 

my solution (60ms, 90.37%)

这道题我给出了两种方案, 递归和迭代

对于迭代, 我将每一级的元素都保留, 然后用作下一次迭代

递归的话, 因为如果只是单节点传参, 始终会面临有缝隙的情况, 所以用双节点传参

递归的代码更加简洁, 我推荐使用递归

emmmm... 速度上还好, 但是内存上就很不能接受了

(我很好奇, 代码量已经很少了, 而且递归中也不会产生多余的操作)

(难道是在 perfect binary tree 上能有什么绚丽的操作么?)

 

best solution

哦哦哦, 用的是迭代的方式, 只不过他用了队列

而且用了size, 这样也就不需要一个新的容器了, 很不错 -v-

不过既然题说了是 perfect binary tree, 而且next默认为空, 那么可以稍微改良一下

细节在于:

  1. 如果是空节点, 少了一个空 queue 的分配时间
  2. 不用再去赋值 nullptr 了
  3. 少了一个 cur->right 的判断, 因为题目说了是 perfect binary tree

PS: 我最后用这个答案再试了一次, 发现结果和我用递归的结果相差无几...

可能这是增加了测试用例或者改了题的结果? 毕竟 TreeLinkNode 变为了 Node