序列化二叉树
序列化二叉树
http://www.nowcoder.com/questionTerminal/cf7e25aa97c04cc1a68c8f040e71fb84
#python非递归解法，可能思路比较麻烦
class Solution:
def Serialize(self, root):
# write code here
#先序遍历二叉树
if not root:
return ['#']
stack=[]
node=root
value=[]
while node&nbs***bsp;stack:
while node:
value.append(str(node.val)+'!')
stack.append(node)
node=node.left
value.append('#')
node=stack.pop()
node=node.right
value.append('#')
return ''.join(value)
def Deserialize(self, s):
# write code here
if s=='#':
return None
node1=TreeNode(0)
root=node1
stack=[]
i=0
temp=0
while len(s)>1&nbs***bsp;stack:
if s[i]=='!':
val=int(s[:i])
s=s[i+1:]
node=TreeNode(val)
stack.append(node)
if temp==0:
node1.left=node
node1=node
else:
node1.right=node
node1=node
i=0
temp=0
elif s[i]=='#':
s=s[i+1:]
node1=stack.pop(-1)
temp=1
i=0
else:
i=i+1
return root.left
