LeetCode/inorderTraversal.py at master · SimonFans/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
class Node:
    def __init__(self,data):
       self.left = None
       self.right = None
       self.data = data


class solution1:

    def inorderTraversal(self,root):
        ans=[]
        self.dfs(root,ans)
        return ans


    def dfs(self,root,ans):
        if not root: return
        self.dfs(root.left, ans)
        ans.append(root.data)
        self.dfs(root.right, ans)

class solution2:
    def inorderTraversal(self,root):
        if not root: return []
        ans,q=[],[]
        self.allLeftStack(root,q)
        while q:
            t=q.pop()
            ans.append(t.data)
            if t.right:
                self.allLeftStack(t.right,q)
        return ans


    def allLeftStack(self,root,q):
        while root:
            q.append(root)
            root=root.left

root=Node(1)
root.right=Node(2)
root.right.left=Node(3)
test=solution1()
test2=solution2()
print(test.inorderTraversal(root))
print(test2.inorderTraversal(root))