1 题目
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
2 解析
二叉树前序遍历的顺序为：
先遍历根节点；
随后递归地遍历左子树；
最后递归地遍历右子树。
二叉树中序遍历的顺序为：
先递归地遍历左子树；
随后遍历根节点；
最后递归地遍历右子树。
在「递归」地遍历某个子树的过程中，我们也是将这颗子树看成一颗全新的树，按照上述的顺序进行遍历。挖掘「前序遍历」和「中序遍历」的性质，我们就可以得出本题的做法。
3 Python实现
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None # 判空
def create_tree(inorder):
x = preorder.pop(0) # 每次取前序列表最左端的元素
node = TreeNode(x) # 用该元素生成一个node
idx = inorder.index(x) # 找到该元素在中序列表中的索引
left_l = inorder[:idx] # 用该元素分割中序列表
right_l = inorder[idx+1:]
node.left = create_tree(left_l) if left_l else None
node.right = create_tree(right_l) if right_l else None
# 一直探索到最底层的最左端的叶子，然后从下往上一层层返回
return node
return create_tree(inorder)
