先序遍歷
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
result = []
stack = []
while root or len(stack) > 0:
while root:
result.append(root.val)
stack.append(root)
root = root.left
cur = stack.pop()
root = cur.right
return result
中序遍歷
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
result = []
stack = []
while root or len(stack) > 0:
while root:
stack.append(root)
root = root.left
cur = stack.pop()
result.append(cur.val)
root = cur.right
return result
后序遍歷
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
result = []
stack = []
prev = None
while root or len(stack) > 0:
while root:
stack.append(root)
root = root.left
cur = stack.pop()
# 如果該節(jié)點(diǎn)存在右子樹，且右子樹未被訪問爵嗅，則將該節(jié)點(diǎn)重新壓入棧中
if cur.right and cur.right != prev:
stack.append(cur)
root = cur.right
else:
result.append(cur.val)
prev = cur
root = None
return result
當(dāng)做一個(gè)記錄握巢，如果大家需要解釋思路的話敞曹，不妨留言冯键，我再補(bǔ)上思路～
