Simple and clear python solution with explain

  • 7

    I use a additional function addLevel to record the level number of nodes, then according to the level number, I can easily deal with the level order, see the code for details

    # Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # @param root, a tree node
        # @return a list of lists of integers
        def zigzagLevelOrder(self, root):
            ans = []
            self.addLevel(ans, 0, root)#level from 0
            return ans
        def addLevel(self, ans, level, root):
            if not root:
            elif len(ans) <= level:
            elif not level%2:#if it is an even level, then then level ans should be inversed, so I use extend founction
                ans[level].insert(0,root.val)# if it is an odd level, then level ans should be ordinal, so I use insert function
            self.addLevel(ans, level + 1, root.left)
            self.addLevel(ans, level + 1, root.right)

  • 0

    similar idea of checking even/odd, but avoid recursion.

            if not root:
                return []
            res,level,count = [],[root],0
            while level:
                res.append([node.val for node in level]) if count%2 == 0 else res.append([node.val for node in level[::-1]])     
                temp = []
                for node in level:
                level = [newnode for newnode in temp if newnode]
                count += 1
            return res

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.