94 Binary Tree Inorder Traversal
二叉樹中序遍歷的循環(huán)解
常規(guī)思路：
向左找到盡頭，彈出一個節(jié)點，指針指向彈出節(jié)點的右孩子 繼續(xù)循環(huán)
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
# if not root:
# return []
res, stack = [], []
p = root
while stack or p: # 中序遍歷處理完左側(cè)分支和根節(jié)點之后 棧空 所以只用stack做條件不合理
while p:
stack.append(p)
p = p.left
cur = stack.pop() # 左邊走到盡頭 彈出最左節(jié)點
res.append(cur.val)
# while stack and not cur.right: # 希望彈出的節(jié)點的右孩子存在 這樣就找到一個接盤俠 類似于遞歸的感覺
# cur = stack.pop() # 但是你怎么能保證就存在呢? p 還是有可能是空的 所以不用折騰
# res.append(cur.val)
p = cur.right # 很像遞歸
return res
將兩層while循環(huán)簡化成一層 仔細分析和上面的代碼思路一抹一樣
def inorderTraversal(self, root):
res, stack = [], []
p = root # 定義一個指針
while stack or p:
if p: # 進棧 往左
stack.append(p)
p = p.left
else: # 出棧 往右 (左邊走到盡頭)
node = stack.pop()
res.append(node.val)
p = node.right # 嘗試向右邊跑 如果這個節(jié)點存在 就是遞歸 不存在 就繼續(xù)彈出棧內(nèi)節(jié)點
return res
節(jié)點狀態(tài)標記法
中序遍歷順序：左根右
難點在于訪問到根節(jié)點的時候并不是現(xiàn)在就要處理該節(jié)點（打印該節(jié)點）
而是要去該節(jié)點的左孩子繼續(xù)向下訪問，
只有當左孩子部分全部處理完畢，再次訪問到根節(jié)點的時候才是處理根節(jié)點的時候
所以給每一個節(jié)點設(shè)置一個狀態(tài)，用于標記該節(jié)點之前是否見過，當某個節(jié)點第二次訪問的時候就是該處理的時候
def inOrder(root):
res, stack = [], [(root, False)]
while stack:
node, vis = stack.pop()
if node:
if vis:
res.append(node.val)
else: # 注意堆棧元素順序和根左右恰好相反
stack.append((node.right, False))
stack.append((node, True))
stack.append((node.left, False))
return res
二叉樹前序遍歷、后序遍歷循環(huán)解 leetcode 144 145
對于前序遍歷，因為根節(jié)點一開始就被用掉，所以很方便
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res, stack = [], [root]
while stack:
node = stack.pop()
if node:
# pre-order, right first 這樣left位于棧頂 所以是根左右
res.append(node.val)
stack.append(node.right)
stack.append(node.left)
return res
對于后序遍歷 根節(jié)點最后處理 所以需要一直在棧底
節(jié)點狀態(tài)標記法
對于每一個節(jié)點給一個狀態(tài)，用于標記這個節(jié)點是第一次訪問還是第二次訪問，第二次訪問才是真正處理該節(jié)點的時候（打印該節(jié)點）
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res, stack = [], [(root, False)]
while stack:
node, vis = stack.pop()
if node:
if vis: # 左右孩子處理完畢
res.append(node.val)
else:
stack.append((node, True)) # 成功地將根節(jié)點放在了棧底
stack.append((node.left, False))
stack.append((node.right, False))
return res
