FilesExpand file tree

master

/

flatten-binary-tree-to-linked-list.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

77 lines (72 loc) · 1.84 KB

master

/

flatten-binary-tree-to-linked-list.py

Copy path

Top

File metadata and controls

• Code
• Blame

77 lines (72 loc) · 1.84 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

# Time: O(n)

# Space: O(h), h is height of binary tree

#

# Given a binary tree, flatten it to a linked list in-place.

#

# For example,

# Given

#

# 1

# / \

# 2 5

# / \ \

# 3 4 6

# The flattened tree should look like:

# 1

# \

# 2

# \

# 3

# \

# 4

# \

# 5

# \

# 6

#

# 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 nothing, do it in place

def flatten(self, root):

return self.flattenRecu(root, None)

def flattenRecu(self, root, list_head):

if root != None:

list_head = self.flattenRecu(root.right, list_head)

list_head = self.flattenRecu(root.left, list_head)

root.right = list_head

root.left = None

return root

else:

return list_head

class Solution2:

list_head = None

# @param root, a tree node

# @return nothing, do it in place

def flatten(self, root):

if root != None:

self.flatten(root.right)

self.flatten(root.left)

root.right = self.list_head

root.left = None

self.list_head = root

return root

if __name__ == "__main__":

root = TreeNode(1)

root.left = TreeNode(2)

root.left.left = TreeNode(3)

root.left.right = TreeNode(4)

root.right = TreeNode(5)

root.right.right = TreeNode(6)

result = Solution().flatten(root)

print result.val

print result.right.val

print result.right.right.val

print result.right.right.right.val

print result.right.right.right.right.val

print result.right.right.right.right.right.val