题目：树的后序遍历
解法：
一共尝试了 3 种解法：
- 使用两个 Map 记录是否访问过了左右子树（当然也可以放到一个 Map 中来）
- 只用一个栈以及上次访问的节点做后序遍历
- 传统的递归方法，用于验证
class Node():
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def lastVist(node):
s = [node]
l = {}
r = {}
while len(s) != 0:
front = s[-1]
if front.left != None and front not in l.keys():
s.append(front.left)
l[front] = True
elif front.right != None and front not in r.keys():
s.append(front.right)
r[front] = True
else:
print front.val
s.pop()
def lastVist2(node):
s = [node]
p = None
while len(s) > 0:
tmp = s[-1]
while tmp.left is not None and tmp.left is not p:
s.append(tmp.left)
tmp = tmp.left
while True:
if tmp.right == p or tmp.right == None:
print tmp.val
p = tmp
s = s[:-1]
if len(s) > 0:
tmp = s[-1]
else:
break
else:
s.append(tmp.right)
break
def lastVist3(node):
if node == None:
return
lastVist3(node.left)
lastVist3(node.right)
print node.val
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n1.right = n2
n2.left = n3
n2.right = n4
lastVist(n1)
print 'vvvv'
lastVist2(n1)
print 'vvvv'
lastVist3(n1)
- EOF -