说一点：遇到这种层次遍历（不管他什么奇葩要求），思路只有一条：那就是使用【两个辅助栈】轻松解决

WechatIMG23.jpeg

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return None
        stack1 = [root]
        stack2 = []
        ret = []

        while stack1 or stack2:
            if stack1:
                tmpList = []
                while stack1:
                    tmp = stack1[0]
                    tmpList.append(tmp.val)
                    if tmp.left:
                        stack2.append(tmp.left)
                    if tmp.right:
                        stack2.append(tmp.right)
                    del stack1[0]
                ret.append(tmpList)
            
            if stack2:
                tmpList = []
                while stack2:
                    tmp = stack2.pop()
                    tmpList.append(tmp.val)
                    if tmp.right:
                        stack1.insert(0,tmp.right)
                    if tmp.left:
                        stack1.insert(0,tmp.left)
                ret.append(tmpList)
        return ret