103-binary-tree-zigzag-level-order-traversal.py

"""
Problem Link: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Given a binary tree, return the zigzag level order traversal of its nodes' values. 
(ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],
 3
 / \
 9 20
 / \
 15 7
return its zigzag level order traversal as:
[
 [3],
 [20,9],
 [15,7]
]
"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
classSolution:
defzigzagLevelOrder(self, root: TreeNode) ->List[List[int]]:
res= []
ifnotroot:
returnres

defhelper(root, level=0):
ifnotroot:
return

iflen(res) ==level:
res.append([])

helper(root.left, level+1)
helper(root.right, level+1)
ifnotlevel%2:
res[level].append(root.val)
else:
res[level].insert(0, root.val)

helper(root)
returnres


classSolution1:
defzigzagLevelOrder(self, root: TreeNode) ->List[List[int]]:
res= []
ifnotroot:
returnres

depth=1
level= [root]
whilelevel:
new_level= []
cur_level= []
flag=depth%2
fornodeinlevel:
ifflag:
cur_level.append(node.val)
else:
cur_level.insert(0, node.val)
ifnode.left:
new_level.append(node.left)
ifnode.right:
new_level.append(node.right)

level=new_levelifnew_levelelseNone
res.append(cur_level)
depth+=1

returnres