Leet_Code/0145_binary_tree_post_order_traversal.py at master · Kcheung42/Leet_Code · 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
109
110
111
#------------------------------------------------------------------------------
# Question: 0145_binary_tree_post_order_traversal.py
#------------------------------------------------------------------------------
# tags:
'''
Given a binary tree, return the postorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]
Follow up: Recursive solution is trivial, could you do it iteratively?

'''

#------------------------------------------------------------------------------
# Solutions
#------------------------------------------------------------------------------
from typing import *
from test_utils.BinaryTree import TreeNode, BinaryTree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class SolutionRecur:
    '''
    Time:
    Space:
    '''
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        def recurUtil(root, result):
            if root is None:
                return
            recurUtil(root.left, result)
            recurUtil(root.right, result)
            result.append(root.val)

        result = []
        recurUtil(root, result)
        return result


class SolutionIter:
    '''
    Time:
    Space:
    '''
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        stack = [root]
        result = []
        while stack:
            root = stack.pop()
            result.append(root.val)
            if root.left is not None:
                stack.append(root.left)
            if root.right is not None:
                stack.append(root.right)
        return result[::-1]


class SolutionIter2:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        stack = [root]
        result = []
        seen = set([])
        while stack:
            root = stack.pop()
            if root in seen:
                result.append(root.val)
            elif root:
                seen.add(root)
                stack.append(root)
                stack.append(root.left)
                stack.append(root.right)
        return result


#------------------------------------------------------------------------------
# Tests
#------------------------------------------------------------------------------
import unittest

class TestSolution(unittest.TestCase):
    def test_simple(self):
        root = [1,None,2,None,None,3]
        root = BinaryTree(root).root

        s = SolutionRecur()
        self.assertEqual(s.postorderTraversal(root), [3,2,1])

        s = SolutionIter()
        self.assertEqual(s.postorderTraversal(root), [3,2,1])

        s = SolutionIter2()
        self.assertEqual(s.postorderTraversal(root), [3,2,1])


unittest.main(verbosity=2)