剑指 Offer 32

BFS模板的应用。

总结的DFS、BFS模板参考：https://www.cnblogs.com/panweiwei/p/13065661.html

class Solution(object):
    # 思路：
    #   层序遍历，套用模板，百试不爽。
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        ans = []
        stack = [root]
        # 外层while遍历树的层数
        while stack:
            temp = []
            sizeStack = len(stack)
            # 内层for遍历每一层（当前层）的所有节点
            for i in range(sizeStack):
                node = stack.pop(0)
                temp.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
            ans.append(temp)
        return ans