LeetCode-Python-103. ツリーのジグザグ階層の遍歴

1417 ワード

ツリーを2つ指定し、ノード値を返すのこぎり階層を巡ります.(すなわち、左から右へ、右から左へと次の層を遍歴し、このようにして層と層の間を交互に行う).
例えば、所与の二叉木[3,9,20,null,null,15,7]は、
    3
   / \
  9  20
    /  \
   15   7

ジグザグ階層を返します.
[
  [3],
  [20,9],
  [15,7]
]

考え方:
ツリーのレイヤシーケンスを巡回するか、変数lor(left or right)を追加して、現在のレイヤが左端から始まるか、右端から始まるかを判断するだけです.
# 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]]
        """
        queue = [root]
        lor = 0 # 0 for left and 1 for right
        res = list()
        if not root:
            return []
        while(queue):
            next_queue = list()
            layer = list()
            
            for node in queue:
                if node.left:
                    next_queue.append(node.left)
                if node.right:
                    next_queue.append(node.right)
                
                layer.append(node.val)

            if not lor: # left
                res.append(layer)
            else:
                res.append(layer[::-1])
            
            lor = 1 - lor
            queue = next_queue
        return res