python-leetcode/binary-tree-zigzag-level-order-traversal.py at master · mindheist/python-leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
# 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,#,#,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(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]]

        """
        # Using a regular level order traversal (either by inverting the order or insertion) or using a stack
        # The solution implemented so far is a little hacked, I did a regular level order traversal and
        # reversed alternate entries in the list to f list

        #Step 1 : levelOrder traversal
        levelOrder_list = self.levelOrder(self.root)
        # Step 2 : Reverse the Level Order traversal
        for i in xrange(len(levelOrder_list)):
            if i%2 == 1:
                levelOrder_list[i] = levelOrder_list[i][::-1]
        return levelOrder_list

    def levelOrder(self,root):
        self.root = root
        if self.root == None:
            return []
        else:
            processing_queue , results = [self.root],[]
            while processing_queue:
                level_vals , length = [],len(processing_queue)
                for i in xrange(length):
                    temp_node = processing_queue[0]
                    level_vals.append(temp_node.val)
                    if temp_node.left:
                        processing_queue.append(temp_node.left)
                    if temp_node.right:
                        processing_queue.append(temp_node.right)
                    processing_queue.pop(0)
                results.append(level_vals)
            return results

class Solution(object):
    def zigzagLevelOrder(self, root):
        self.root = root
        if self.root == None:
            return []
        else:
            processing_queue , results = [self.root],[]
            order = "even"
            while processing_queue:
                if order == "odd":
                    level_vals , length = [],len(processing_queue)
                    for i in xrange(length):
                        temp_node = processing_queue[0]
                        level_vals.append(temp_node.val)
                        if temp_node.left:
                            processing_queue.append(temp_node.left)
                        if temp_node.right:
                            processing_queue.append(temp_node.right)
                        processing_queue.pop(0)
                    results.append(level_vals)
                    order = "even"
                if order == "even":
                    level_vals , length = [],len(processing_queue)
                    for i in xrange(length):
                        temp_node = processing_queue[0]
                        level_vals.append(temp_node.val)
                        if temp_node.right:
                            processing_queue.append(temp_node.right)
                        if temp_node.left:
                            processing_queue.append(temp_node.left)
                        processing_queue.pop(0)
                    results.append(level_vals)
                    order = "odd"
            if results[len(results)-1]==[]:
                return results[:-1:]
            else:
                return results

# Fails in the following test - should understand serialization more to figure this out.
# Input:
# [1,2,3,4,null,null,5]
# Output:
# [[1],[3,2],[5,4]]
# Expected:
# [[1],[3,2],[4,5]]