非递归遍历二叉树的方法

前言

统一的简洁的二叉树非递归遍历写法

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def preOrder(root,path):
s = []
if not root:
return s
s.push([root,False])
while not s:
node, visited = s[-1]
s.pop()
if not node:
continue
if visited:
path.append(node)
else:
s.append([node.right,False])
s.append([node.left,False])
s.append([node,True])
return path

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def inOrder(root,path):
s = []
if not root:
return s
s.push([root,False])
while not s:
node, visited = s[-1]
s.pop()
if not node:
continue
if visited:
path.append(node)
else:
s.append([node.right,False])
s.append([node,True])
s.append([node.left,False])
return path

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def postOrder(root,path):
s = []
if not root:
return s
s.push([root,False])
while not s:
node, visited = s[-1]
s.pop()
if not node:
continue
if visited:
path.append(node)
else:
s.append([node,True])
s.append([node.right,False])
s.append([node.left,False])
return path