力扣——二叉树的前中后序遍历

二叉树主要有两种遍历方式：

• 深度优先遍历：先往深走，遇到叶子节点再往回走。
• 广度优先遍历：一层一层的去遍历，也就是常说的层遍历。

在深度优先遍历中：有三个顺序，前中后序遍历，这中间的"前中后"指的是遍历父节点的先后顺序，且左节点永远在右节点前面遍历。

• 前序遍历(父左右)：F、B、A、D、C、E、G、I、H。

• 中序遍历(左父右)：A、B、C、D、E、F、G、H、I。

• 后序遍历(左右父)：A、C、E、D、B、H、I、G、F。

图片来源：https://zh.m.wikipedia.org/wiki/%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86
在树的遍实现方法中，有两种比较主流：迭代和递归。下面以力扣的三道题目作为例子：

• 144.二叉树的前序遍历
• 94.二叉树的中序遍历
• 145.二叉树的后序遍历

递归：

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, val=0, left=None, right=None):#  self.val = val#  self.left = left#  self.right = right#前序class Solution:    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: answer = [] def dfs(node) :     if node is None :  return    answer.append(node.val)     dfs(node.left)     dfs(node.right) dfs(root) return answer  #中序 class Solution:    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: answer = [] def dfs(node) :     if node is None :  return      dfs(node.left)     answer.append(node.val)     dfs(node.right) dfs(root) return answer#后序class Solution:    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def dfs(node) :     if node is None :  return    dfs(node.left)     dfs(node.right)     answer.append(node.val) answer = [] dfs(root) return answer

迭代：

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, val=0, left=None, right=None):#  self.val = val#  self.left = left#  self.right = right#前序class Solution:    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if root is None :     return []  stack = [] result = [] stack.append(root) while stack :     node = stack.pop()     result.append(node.val)     if node.right :  stack.append(node.right)   if node.left :  stack.append(node.left) return result#中序class Solution:    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if root is None :     return [] result = [] stack = [] curr = root  while curr or stack :     #访问最左边节点     if curr :  stack.append(curr)  curr = curr.left   else :  node = stack.pop()  result.append(node.val)  #访问栈顶元素的右边节点  curr = node.right  return result#后序class Solution:    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if root is None :     return [] result = [] stack = [] stack.append(root) while stack :     node = stack.pop()     result.append(node.val)     if node.left :  stack.append(node.left)   if node.right :  stack.append(node.right) return result[ : : -1]