
1 因为是perfect binary tree,所以所有叶子节点都在一个level上,而且每一个internal node都有两个children
2 BFS不能用queue来做,因为会有extra space
3 最外面一个while循环,循环条件是root.left
4 将当前节点root的root.left和root.right连接起来后(root.left.next=root.right),我们需要再将root.right和root.next.left连接起来,直到root.next不再存在
5 在init里,self.next = None已经
6 if not root: return 不能写成if not root: return None 这道题并没有返回值,不能用return None

Time complexity: O(n)
Space complexity: O(n) since the last level has n/2 nodes

Time complexity: O(n)
Space complexity: O(1)
Tree上的node一开始就是定义成有next pointer的,不需要额外再处理了