python 迭代+递归+层序遍历二叉树

迭代遍历二叉树 中序遍历 class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: res = [] stack = [] cur = root # 中序，模板：先用指针找到每颗子树的最左下角，然后进行进出栈操作 while stack or cur: while cur: stack.append(cur) cur = cur.left cur = stack.pop() res.append(cur.val) cur = cur.right return res 前序遍历 class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: res = [] stack = [] cur = root while stack or cur: while cur: res.append(cur.val) stack.append(cur) cur = cur.left cur = stack.pop() cur = cur.right return res 后序遍历 class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: res = [] stack = [] cur = root while stack or cur: while cur: res.append(cur.val) stack.append(cur) cur = cur.right cur = stack.pop() cur = cur.left return res[::-1] 递归遍历 class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: def dfs(cur): if not cur: return # 前序递归 res.append(cur.val) dfs(cur.left) dfs(cur.right) # # 中序递归 # dfs(cur.left) # res.append(cur.val) # dfs(cur.right) # # 后序递归 # dfs(cur.left) # dfs(cur.right) # res.append(cur.val) res = [] dfs(root) return res 层序遍历 class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] queue, res = [root], [] while queue: n = len(queue) tmp = [] for _ in range(n): node = queue.pop(0) tmp.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(tmp) return res