基本概念

在这之前我们首先得了解什么是前序、中序和后序遍历。

以上图这张二叉树为例：

前序遍历： 遍历顺序为根节点->左子节点->右子节点，每次先遍历根节点，遍历结果为1 2 4 5 3 6 7

中序遍历： 中序遍历顺序为左子节点->根节点->右子节点，遍历结果为4 2 5 1 6 3 7

后序遍历: 后序遍历的顺序为左子节点->右子节点->根节点, 遍历结果为4 5 2 6 7 3 1

递归解法

递归解法是解决二叉树遍历问题最简单的一种方式，只需将递归函数里的res.append(root.val)放到不同的位置即可。

def dfs(root):
  if not root: return []
  res.append(root.val)
  dfs(root.left)
  dfs(root.right)

前序遍历

class Solution:
  def preorderTraversal(self, root: TreeNode)->List[int]:
      res = []
      def dfs(root):
          nonlocal res
          if not root: return
          res.append(root.val)
          dfs(root.left)
          dfs(root.right)
      dfs(root)
      return res

中序遍历

class Solution:
  def preorderTraversal(self, root: TreeNode)->List[int]:
      res = []
      def dfs(root):
          nonlocal res
          if not root: return
          dfs(root.left)
          res.append(root.val)
          dfs(root.right)
      dfs(root)
      return res

后序遍历

class Solution:
  def preorderTraversal(self, root: TreeNode)->List[int]:
      res = []
      def dfs(root):
          nonlocal res
          if not root: return
          dfs(root.left)
          dfs(root.right)
          res.append(root.val)
      dfs(root)
      return res

迭代解法

前序遍历

解法1 算法过程

这套解题思路与上面的递归法基本一致，用栈的方式来替代递归的层次。

  1. 初始化栈，将根节点入栈
  2. 当栈不为空时：
    • 弹出栈顶元素，将值添加到结果res中
    • 如果右子树不为空，将右子树入栈
    • 如果左子树不为空，将左子树入栈

为什么是先入右子树？因为栈的先进后出特性，使得在栈中的顺序为右子树->左子树，最终放入到结果res中的顺序则是左子树->右子树

class Solution:
  def preorderTraversal(self, root: TreeNode)->List[int]:
    if not root: return []
    stack,res = [root],[]
    while stack:
      cur = stack.pop()
      if cur:
        res.append(cur.val)
        if cur.right: stack.append(cur.right)
        if cur.left: stack.append(cur.left)
    return res

解法2 迭代模板算法

解题思路：

模板算法的思路与上面的不同，初始时先将根节点和所有左子树入栈并放入到结果中，直至cur为空。

while cur:
  res.append(cur.val)
  stack.append(cur)
  cur = cur.left

这样我们的栈中就存入的所有的左子树，接下来每弹出一个左子树tmp就去寻找它的右子树并赋值给cur。此时cur又不为空了，又重新进到上面的while循环中。

class Solution:
  def preorderTraversal(self, root: TreeNode)->List[int]:
      if not root: return []
      stack, res, cur = [], [], root
      while stack or cur:
         while cur:
            stack.append(cur)
            res.append(cur.val)
            cur = cur.left
        tmp = stack.pop()
        cur = tmp.right
      return res

中序遍历

模板解法思路和前序遍历一样，只不过是放入结果的顺序不同。

class Solution:
  def preorderTraversal(self, root: TreeNode)->List[int]:
      if not root: return []
      stack, res, cur = [], [], root
      while stack or cur:
        while cur:
          stack.append(cur)
          cur = cur.left
        tmp = stack.pop()
        res.append(tmp.val)
        cur = tmp.right
     return res

后序遍历

后序遍历我们可以借助前序遍历的思路，最后再将结果翻转过来即可，期间要注意的是左右子树的顺序需与前序遍历相反。

根->右->左 翻转后变成左->右->根

class Solution:
  def preorderTraversal(self, root: TreeNode)->List[int]:
     if not root: return []
      stack, res, cur = [], [], root
      while stack or cur:
        while cur:
          res.append(cur.val)
          stack.append(cur)
          cur = cur.right
        tmp = stack.pop()
        cur = tmp.left
     return res[::-1]

后序遍历迭代解法的标准方案

这个解法稍稍不同的是需要添加一个标识flag并以元组的形式与节点一起放入到栈中，然后每次从栈中弹出时，如果flag为0，则需要将flag变为1并连同该节点入栈，只有当flag为1时才能将节点放入到结果中。

class Solution:
  def preorderTraversal(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