LeetcodePython/flat_tree_to_llist.py at master · 1code/LeetcodePython · 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
#!/usr/bin/env python
'''
Leetcode: Flatten Binary Tree to Linked List
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
If you notice carefully in the flattened tree,
each node's right child points to the next node of a pre-order traversal.
'''
from __future__ import division
import random
from BinaryTree import Node, root


### In-order traversal without using recursion or stack, in place
### (Morris traversal)
# 1. cur = root
# 2. if cur has no left-child
#     2.1 print cur.value
#     2.2 cur --> cur.right
# 3. else:
#     3.1 cur --> the right most child of the left subtree
#     3.2 cur --> cur.left
def morris_traversal(root):
    cur = root
    while cur:
        if cur.left is not None:
            rightmost_in_left = cur.left
            while rightmost_in_left.right:
                rightmost_in_left = rightmost_in_left.right
            rightmost_in_left.right = cur
            cur_left = cur.left
            cur.left = None
            cur = cur_left
        else: # visit right child
            # no left child, it is the turn to visit the root!
            print cur.value,
            cur = cur.right


# For each node:
# 1. cur = root
# 2. visit cur
# 3. if cur has no left-child:
#     3.1 cur = cur.right
# 4. else:
#     4.1 move cur's right-child to the rightmost child of its left subtree
#     4.2 cur = cur.left
def inplace_preorder_traversal(root):
    cur = root
    while cur:
        print cur.value,
        if cur.left:
            if cur.right:
                rightmost_in_left = cur.left
                while rightmost_in_left.right:
                    rightmost_in_left = rightmost_in_left.right
                rightmost_in_left.right = cur.right
            cur.right = None
            cur = cur.left
        else:
            cur = cur.right


def flatten(root):
    cur = root
    # pre-order in-place traversal
    while cur:
        #print cur.value,
        if cur.left:
            if cur.right:
                rightmost_in_left = cur.left
                while rightmost_in_left.right:
                    rightmost_in_left = rightmost_in_left.right
                rightmost_in_left.right = cur.right
            cur.right = None
            cur = cur.left
        else:
            cur = cur.right
    print root
    # move all left child to be right child
    cur = root
    while cur:
        if cur.left:
            cur.right = cur.left
            cur.left = None
        cur = cur.right
    print root


if __name__ == '__main__':
    print root
    flatten(root)