Binary Tree Level Order Traversal

思路

从某种意义上讲，binary tree level order traversal和 binary dfs traversal是一样的，因为这两种算法都是自上而下的考虑问题。这也显示出了level order traversal和divide and conquer的区别，level order traversal无法做到先解决子问题，然后return 给prarent问题。这也是我们判断用什么思路解决binary tree的关键。如果希望自下而上，那么使用divide and conquer，如果希望自上而下，那么请使用level order traversal or dfs traversal

题型

• 横向遍历
• 横向操作: 这种题之所以比较复杂是因为我们有两个方向的遍历，从外层是从上到下，内层是从左到右。而关键的methods就两个，hasChild()和hasNext（）。注意为了code方便，我们最好吧parent, cur and next都设置成类变量。这样每次判断完以后停留的位置就是我们下次想要开始的地方。

  题目

横向遍历

• Leetcode 102. Binary Tree Level Order Traversal
• Leetcode 107. Binary Tree Level Order Traversal II
• Leetcode 199. Binary Tree Right Side View
• Leetcode 314. Binary Tree Vertical Order Traversal (Facebook店面，这道题的核心就是BFS的时候记录每个node的横向offset，并且用HashMap存储offset相同的nodes)

横向操作

• Leetcode 116. Populating Next Right Pointers in Each Node
• Leetcode 117. Populating Next Right Pointers in Each Node II