python3 參考這篇題解：二叉樹遍歷https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/tu-jie-er-cha-shu-de-si-chong-bian-li-by-z1m/
前序遍歷：根->左->右
LeetCode?144.二叉樹的前序遍歷
迭代解法：（借助棧）
class?Solution:
????def?preorderTraversal(self,?root:?TreeNode)?->?List[int]:
????????if?not?root:?return?[]
????????stack,?res=[root],?[]
????????while?stack:
????????????node=stack.pop()
????????????if?node:
????????????????res.append(node.val)
????????????????if?node.right:
????????????????????stack.append(node.right)
????????????????if?node.left:
????????????????????stack.append(node.left)
????????return?res
遞歸解法：
class?Solution:
????def?preorderTraversal(self,?root:?TreeNode)?->?List[int]:
????????res=[]
????????def?preorder(root):
????????????nonlocal?res
????????????if?not?root:
????????????????return
????????????res.append(root.val)
????????????preorder(root.left)
????????????preorder(root.right)
????????preorder(root)
????????return?res
中序遍歷：左->根->右
Leetcode?94. 二叉樹的中序遍歷
遞歸解法：
class?Solution:
????def?inorderTraversal(self,?root:?TreeNode)?->?List[int]:
????????if?not?root:?return?[]
????????stack,?res=?[(0,root)],?[]
????????while?stack:
????????????flag,?node=stack.pop()
????????????if?not?node:?continue
????????????if?flag==1:?res.append(node.val)
????????????else:
????????????????stack.append((0,node.right))
????????????????stack.append((1,node))
????????????????stack.append((0,node.left))
????????return?res
遞歸解法：
class?Solution:
????def?inorderTraversal(self,?root:?TreeNode)?->?List[int]:
????????res=[]
????????def?inorder(root):
????????????nonlocal?res
????????????if?not?root:
???????????????return
????????????inorder(root.left)
????????????res.append(root.val)
????????????inorder(root.right)
????????inorder(root)
????????return?res
后序遍歷：左->右->根
Leetcode?145. 二叉樹的后序遍歷
迭代解法：
class?Solution:
????def?postorderTraversal(self,?root:?TreeNode)?->?List[int]:
????????if?not?root:?return?[]
????????stack,?res=?[(0,root)],?[]
????????while?stack:
????????????flag,?node=stack.pop()
????????????if?not?node:?continue
????????????if?flag==1:?res.append(node.val)
????????????else:
????????????????stack.append((1,node))
????????????????stack.append((0,node.right))
????????????????stack.append((0,node.left))
????????return?res
遞歸解法：
class?Solution:
????def?postorderTraversal(self,?root:?TreeNode)?->?List[int]:
????????res=?[]
????????def?postorder(root):
????????????nonlocal?res
????????????if?not?root:
????????????????return
????????????postorder(root.left)
????????????postorder(root.right)
????????????res.append(root.val)
????????postorder(root)
????????return?res
層序遍歷：廣度優(yōu)先算法，用隊列
Leetcode102. 二叉樹的層序遍歷
class?Solution:
????def?levelOrder(self,?root:?TreeNode)?->?List[List[int]]:
????????if?not?root:?return?[]
????????res,?q=?[],?[root]
????????while?q:
????????????level=[]
????????????n=?len(q)
????????????for?i?in?range(n):
????????????????node=q.pop(0)
????????????????level.append(node.val)
????????????????if?node.left:
????????????????????q.append(node.left)
????????????????if?node.right:
????????????????????q.append(node.right)
????????????res.append(level)
????????return?res
偽碼：
