LeetCode #102 #107 #103 2018-08-

另一种是以图的广度优先搜索为原型的，在树中称为层序遍历，LeetCode中有三种自顶向下层序，自底向上层序和锯齿层序遍历，对应于Binary Tree Level Order Traversal，Binary Tree Level Order Traversal II和Binary Tree Zigzag Level Order Traversal。

102. Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/description/

这道题要求实现树的层序遍历，其实本质就是把树看成一个有向图，然后进行一次广度优先搜索。这里同样是维护一个队列，只是对于每个结点我们知道它的邻接点只有可能是左孩子和右孩子。算法的时间复杂度是就结点的数量O(n)，空间复杂度是一层的结点数，也是O(n)。
代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        result = []
        if not root:
            return result
        queue = [root]
        cur_num = 1
        next_num = 0
        temp = []
        while queue:
            node = queue.pop()
            temp.append(node.val)
            cur_num -= 1
            if node.left:
                queue.insert(0, node.left)
                next_num += 1
            if node.right:
                queue.insert(0, node.right)
                next_num += 1
            if cur_num == 0:
                result.append(list(temp))
                cur_num = next_num
                temp = []
                next_num = 0
        return result

107. Binary Tree Level Order Traversal II

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/

解法与上一题基本相同，不再赘述。
代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        result = []
        if not root:
            return result
        queue = [root]
        temp = []
        cur = 1
        next = 0
        while queue:
            node = queue.pop()
            temp.append(node.val)
            cur -= 1
            if node.left:
                queue.insert(0, node.left)
                next += 1
            if node.right:
                queue.insert(0, node.right)
                next += 1
            if cur == 0:
                result.append(list(temp))
                temp = []
                cur = next
                next = 0
        return result[::-1]

103. Binary Tree Zigzag Level Order Traversal

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/

这道题其实还是树的层序遍历Binary Tree Level Order Traversal，不过这里稍微做了一点变体，就是在遍历的时候偶数层自左向右，而奇数层自右向左。
在Binary Tree Level Order Traversal中我们是维护了一个队列来完成遍历，而在这里为了使每次都倒序出来，我们很容易想到用栈的结构来完成这个操作。有一个区别是这里我们需要一层一层的来处理（原来可以按队列插入就可以，因为后进来的元素不会先处理），所以这里同时维护新旧两个栈，一个来读取，一个存储下一层结点。总体来说还是一次遍历完成，所以时间复杂度是O(n)，空间复杂度最坏是两层的结点，所以数量级还是O(n)（满二叉树最后一层的结点是n/2个）。
代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        result = []
        if not root:
            return result
        stack = [root]
        level = 1
        temp = []
        while stack:
            cur_stack = []
            while stack:
                node = stack.pop()
                temp.append(node.val)
                if level % 2:
                    if node.left:
                        cur_stack.append(node.left)
                    if node.right:
                        cur_stack.append(node.right)
                else:
                    if node.right:
                        cur_stack.append(node.right)
                    if node.left:
                        cur_stack.append(node.left)
            result.append(list(temp))
            temp = []
            stack = cur_stack
            level += 1
        return result