先序遍历
def preOrder(Tnode):
if Tnode:
stack = [Tnode]
while stack:
cur = stack.pop()
print(cur.val)
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)
先序遍历和层次遍历（广度优先）
- 辅助数据结构不同：栈和队列
- 左右孩子入栈（队列）顺序不一样
中序遍历
def inOrder(Tnode):
stack = []
cur = Tnode
while stack or cur:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
print(cur.val)
cur = cur.right
- 判断当前是否为最左节点
- 判断是否有右孩子
后续遍历
def posOrder(Tnode):
if Tnode:
stack = [Tnode]
help = []
while stack:
cur = stack.pop()
help.append(cur)
if cur.left: # 入栈顺序不同
stack.append(cur.left)
if cur.right:
stack.append(cur.right)
while help: # 逆序输出
print(help.pop().val)
先序遍历和后序遍历：
- 左右孩子入栈顺序相反
- 后序需要额外栈记录顺序并逆序输出
例如：
pre:1-2-3
pos:pre(1-2-3)的入栈顺序不同(1-3-2)-->逆序输出-->(2-3-1)
