先序遍歷
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)
先序遍歷和層次遍歷（廣度優(yōu)先）
- 輔助數(shù)據(jù)結(jié)構(gòu)不同：棧和隊(duì)列
- 左右孩子入棧（隊(duì)列）順序不一樣
中序遍歷
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
- 判斷當(dāng)前是否為最左節(jié)點(diǎn)
- 判斷是否有右孩子
后續(xù)遍歷
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)
