Jeswang's Blog

盲目跟随还是独立去做,To be or not to be?

中序遍历序列建堆

| Comments

题目:给出一个堆的中序遍历的序列,重建这个堆。

主要是要设计好函数的参数与返回值。

解答:

(stack.py) download
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.val = val
        self.rChild = None
        self.lChild = None


a = [3, 2, 4, 1, 3, 5,7,9]


def stack(left, remain, flag):
    if left == None and len(remain) > 0:
        left = Node(remain[0])
        remain = remain[1:]

    if len(remain) == 0:
        return (left, [])
    else:
        tmp = Node(remain[0])
        remain = remain[1:]
        if tmp.val > left.val:
            left.rChild, remain = stack(tmp, remain, left.val)
            return stack(left, remain, 0)
        else:
            if tmp.val < flag:
                remain = [tmp.val] + remain
                return left, remain
            tmp.lChild = left
            tmp.rChild, remain = stack(None, remain, tmp.val)
            return stack(tmp, remain, 0)


def midWalk(node):
    if node == None:
        return
    midWalk(node.lChild)
    print node.val
    midWalk(node.rChild)


(node, remain) = stack(None, a, 0)
midWalk(node)

Comments