二叉树相关问题

同じ人なんて いないから
孤独でも仕方ない
でもね
あぁ 聴きたい 歌や 声が あるから
あぁ 泣いた 本や 映画が あるから
あなたを導く夢はある
照らしてみせてよ

Gifts

Gifts - Superfly

Pre,In,Post Traversal; Successor Node; Serialization; Origami

之前几周都比较水，算法课也没有怎么认真看，最近得慢慢补上来
不过算法还是需要慢慢消化，真正理解并且多复习，记忆才是最重要的

DFS

Pre, In, Post Order Traversal in Binary Tree

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
class Node:
    def __init__(self, data):
        self.value = data
        self.left = None
        self.right = None


def preOrderTraversal(head):
    if head is None:
        return None
    print(head.value + ' ')
    preOrderTraversal(head.left)
    preOrderTraversal(head.right)


def inOrderTraversal(head):
    if head is None:
        return None
    inOrderTraversal(head.left)
    print(head.value + ' ')
    inOrderTraversal(head.right)


def postOrderTraversal(head):
    if head is None:
        return None
    postOrderTraversal(head.left)
    postOrderTraversal(head.right)
    print(head.value + ' ')

Breadth First Search (BFS)

这里是关于一道求树最大宽度的解，本质是用了BFS

这里最核心的BFS是用java写的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void treeBFS(Node head) {
if (head == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.println(cur.value+" ");
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}

此题的python解以及测试：

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
from collections import deque

def breathFirstSearch(head):
    queue = deque()
    if head is None:
        return None
    levelMap = {}
    levelMap[head] = 1
    queue.append(head)

    cLevel = 1
    cNodes = 0 # set to 0 because we need to use +=1 in while to make loop run
    maxa = 0
    while queue:
        cur = queue.popleft()
        level = levelMap.get(cur)

        if level == cLevel:
            cNodes += 1 # nodes on current level +=1
        else:
            print("level: {}, nodes: {}".format(cLevel, cNodes))
            if cNodes > maxa:
                maxa = cNodes
            cLevel += 1
            cNodes = 1 # cNodes is the first element of the level, (it has been popped)

        print("Node: {}, level: {}".format(cur.value, level))
        if cur.left is not None:
            levelMap[cur.left] = level + 1
            queue.append(cur.left)
        if cur.right is not None:
            levelMap[cur.right] = level + 1
            queue.append(cur.right)

    print("level: {}, nodes: {}".format(level, cNodes))

    '''catch the max of the last level: it will not enter the while as all stuffs has been poped'''

    print("the max level is {}".format(max(maxa, cNodes)))


if __name__ == "__main__":
    head = Node(1)
    head.left = Node(2)
    head.right = Node(3)
    head.left.left = Node(4)
    head.left.right = Node(5)
    head.right.left = Node(6)
    head.right.right = Node(7)
    breathFirstSearch(head)

在中序遍历中后继节点与前驱节点的直接查找

A direct way of finding the successor node and previous node in the in-order traversal

S_uccessor:_
Two situations:

  1. the leftest child in the right tree of a node X is the next node in the traversal of node X.
  2. if the X does not have right tree, go to the parent node, and continue if the parent is always the right child of its parent, until it is the left child of the parent Y. this Y is the next node of X. However, there is no such y, means x does not have the next node.
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
''' to find the next node of a node in the in-order traversal'''
class Node:
    def __init__(self, val):
        self.value = val
        self.left = None
        self.right = None
        self.parent = None
'''
two situations:
1. the leftest child in the right tree of a node X is the next node in the traversal of node X
2. if the X does not have right tree, go to the parent node, and continue if the parent
is always the right child of its parent, until it is the left child of the parent Y. this Y
is the next node of X. However, there is no such y, means x does not have the next node.
'''
def findSuccessor(node):
    if node is None:
        return None
    if node.right is not None:
        return getMostLeft(node.right)
    else:
        parent = node.parent
        while parent is not None and node != parent.left:
            node = parent
            parent = node.parent
        return parent

def getMostLeft(node):
    if node is None:
        return None
    while node.left is not None:
        node = node.left
    return node

Previous Node:
Two situations:

  1. if the node has left child, the prev node is rightest of the left child.
  2. if the node X does not have left child, we keep going to its parent. if the parent is also the left child of its parent, keep going until it is the right child of a parent. the parent here is its previous node X.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def getPreviousNode(node):
    if node is None:
        return None
    elif node.left:
        return getMostRight(node.left)
    else:
        parent = node.parent
        while parent and node != parent.right:
            node = parent
            parent = node.parent
        return parent

def getMostRight(node):
    if not node:
        return None
    while node.right:
        node = node.right
    return node

_Serialization and Deserialization

序列化 和 反序列化_

Serialization:
serialize the binary tree in the memory into string and
deserialize it from the string to memory.
Structure and Data should be preserved.

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
class Node:
    def __init__(self, val):
        self.value = val
        self.left = None
        self.right = None

    def __repr__(self):
        return "Node <{}>".format(self.value)

    __str__ = __repr__

'''record a node by _ and do not ignore the None node'''


def preOrderSerialize(head):
    if head is None:
        return '#_'
    output = str(head.value) + "_"
    output += preOrderSerialize(head.left)  # output is waiting for further recursion from the left
    output += preOrderSerialize(head.right)  # waiting for the right
    return output  # return output itself to append to the output on the upper level



from collections import deque

def preOrderDeserialize_String(string):
    values = string.split('_')
    queue = deque()
    for i in values:
        queue.append(i)
    return preOrderDeserialize_Tree_subprocess(queue)


def preOrderDeserialize_Tree_subprocess(queue):
    value = queue.popleft()
    if value == '#':
        return None
    head = Node(int(value))
    head.left = preOrderDeserialize_Tree_subprocess(queue)
    head.right = preOrderDeserialize_Tree_subprocess(queue)
    return head

应用： 一个树是否是另外一个树的子树

1
2
3
4
5
6
7
8
'''
application: is a tree t1 the subtree of another tree t2 ?
answer: serialize both and check t1_string is part of t2_string
'''
def isSubtreeOf(t1, t2):
    t1_string = preOrderSerialize(t1)
    t2_string = preOrderSerialize(t2)
    return t1_string in t2_string

Test:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if __name__ == "__main__":
    head = Node(1)
    head.left = Node(2)
    head.right = Node(3)
    head.left.left = Node(4)
    head.left.right = Node(5)
    head.right.left = Node(6)
    head.right.right = Node(7)
    serial = preOrderSerialize(head)
    print("this is a serialized tree: \n{}".format(serial))
    head = preOrderDeserialize_String(serial)
    print("Now the tree has be deserialized, start to check")
    print(head, head.left, head.right, head.left.left, head.left.right, head.right.left, head.right.right)
    print("\nnow check if t2 is a subtree of t1:")
    head_2 = Node(3)
    head_2.left = Node(6)
    head_2.right = Node(7)
    print(isSubtreeOf(head_2, head))

Origami 折纸问题

这道题需要再实际折一下更好理解

_Fold the paper inwards (always), everytime after the first inward folding, we will have two new fold mark (one inward mark upon and outward mark below every fold marks in current level
(current times of folding))

Solution: the folding process is a tree with inward mark. all heads of left child is inward, and all head of right child is outward_

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def printAllFolds(N):
    printProcess(1, N, True)

def printProcess(i, N, down):  # args: (level, the total times of folding, inwards)
    if i > N:
        return None
    printProcess(i+1, N, True)
    if down:
        print('inwards')
    else:
        print('outwards')
    printProcess(i+1, N, False)

if __name__ == "__main__":
    printAllFolds(2)