基础

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分 。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

二叉树遍历 - 图2

  1. class TreeNode:
  2.     def __init__(self, val=0, left=None, right=None):
  3.         self.val = val
  4.         self.left = left
  5.         self.right = right

尽管二叉树遍历很基础，但却是面试中的高频知识点，尤其是迭代的版本和层序遍历。另外， 不管是迭代版本还是递归版本的二叉树遍历都申请了额外的空间（递归方法申请了系统的栈空间，迭代方法额外申请了栈来储存节点），Morris遍历作为二叉树遍历的进阶方法，实现了O(1)空间复杂度，对一些可以修改成二叉树遍历的问题（比如判断一个树是否为二叉搜索树）可以写出比较秀的代码。
这篇文章整理常见的所有二叉树遍历方法

前序遍历

图中树对应的前序遍历为：1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7，即“根节点 -> 左节点 -> 右节点”，记不住的话想一下读书的顺序，“目录 -> 第一章 -> 第一章第一节 -> 第一章第二节 -> 第二章 -> 第二章第一节 -> 第二章第二节”。

递归版本

时间复杂度O(n) 空间复杂度O(n) （这里的O(n)指的是申请stack的内存开销，res用于记录结果，替换成print也可以，下同）
对于每个节点都会处理3次(回到以自己为头的函数内部)，即打印自身，调用左子树遍历，调用右子树遍历

  1. def preorder(root):
  2.     if not root:
  3.         return None
  4.     print(root.val)
  5.     preorder(root.left)
  6.     preorder(root.right)

迭代版本

时间复杂度O(n) 空间复杂度O(n)
借助一个栈，利用其后进先出的特性完成遍历，大致流程就是沿着头节点一路向下找到左树上的最左节点并将节点依次压栈，在压栈的同时用res数组记录节点值，直到当前节点为空，弹出栈顶节点找右子树，可以画一个栈模拟一下节点进出栈顺序。

  1. def inorderTraversal(self, root): 
  2.     stack, res = [], []
  3.     cur = root
  4.     while stack or cur:
  5.         while cur:
  6.             res.append(cur.val)
  7.             stack.append(cur)
  8.             cur = cur.left
  9.         cur = stack.pop()
  10.         cur = cur.right
  11.     return res

中序遍历

图中树对应的前序遍历为：4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7，即“左节点 -> 根节点 -> 右节点”。

递归版本

时间复杂度O(n) 空间复杂度O(n)
对于每个节点都会处理3次(回到以自己为头的函数内部)，即调用左子树遍历，打印自身，调用右子树遍历

  1. def preorder(root):
  2.     if not root:
  3.         return None
  4.     preorder(root.left)
  5.     print(root.val)
  6.     preorder(root.right)

迭代版本

时间复杂度O(n) 空间复杂度O(n)
借助一个栈，利用其后进先出的特性完成遍历，大致流程就是沿着头节点一路向下找到左树上的最左节点并将节点依次压栈，直到当前节点为空，弹出栈顶节点，用res数组记录节点值，找右子树，可以画一个栈模拟一下节点进出栈顺序。

  1. def inorderTraversal(self, root): 
  2.     stack, res = [], []
  3.     cur = root
  4.     while stack or cur:
  5.         while cur:
  6.             stack.append(cur)
  7.             cur = cur.left
  8.         cur = stack.pop()
  9.         res.append(cur.val)
  10.         cur = cur.right
  11.     return res

后序遍历

图中树对应的前序遍历为：4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1，即“左节点 -> 右节点 -> 根节点”。

递归版本

时间复杂度O(n) 空间复杂度O(n)
对于每个节点都会处理3次(回到以自己为头的函数内部)，即调用左子树遍历，调用右子树遍历，打印自身

  1. def preorder(root):
  2.     if not root:
  3.         return None
  4.     preorder(root.left)
  5.     preorder(root.right)
  6.     print(root.val)

迭代版本

时间复杂度O(n) 空间复杂度O(n)
借助一个栈，利用其后进先出的特性完成遍历，观察后序遍历“左右中”与先序遍历“中左右”，我们不妨先按照“中右左”的顺序遍历，然后逆序输出即可
大致流程就是沿着头节点一路向下找到右树上的最右节点并将节点依次压栈，直到当前节点为空，弹出栈顶节点，用res数组记录节点值，找左子树，可以画一个栈模拟一下节点进出栈顺序。

  1. def inorderTraversal(self, root): 
  2.     stack, res = [], []
  3.     cur = root
  4.     while stack or cur:
  5.         while cur:
  6.             res.append(cur.val)
  7.             stack.append(cur)
  8.             cur = cur.right
  9.         cur = stack.pop()
  10.         cur = cur.left
  11.     return res[::-1]

层序遍历

时间复杂度O(n) 空间复杂度O(n)
借助一个队列queue，利用其先进先出的特性完成遍历，大致流程头节点加入queue，弹出队尾节点用res数组记录当前节点的值，同如果当前节点有左子节点和右子节点就依次加入到的queue中。图中树对应的前序遍历为：1-> 2 -> 3 -> 4 -> 5 -> 6 -> 7，即按层从上到下输出，从左到右遍历。可见Leetcode 102 103

  1.  from collections import deque
  2.  def levelOrder(root: TreeNode) -> List[int]:
  3.       if not root:
  4.          return []
  5.      queue = deque(root)
  6.      res = []
  7.      while queue:
  8.          cur = queue.popleft()
  9.          res.append(cur.val)
  10.          if cur.left:
  11.              queue.append(cur.left)
  12.          if cur.right:
  13.              queue.append(cur.right)
  14.        return res
  1. class Solution:
  2.     def levelOrder(self, root: TreeNode) -> List[List[int]]:
  3.         if not root:
  4.             return []
  5.         nexts = []
  6.         cur = [root]
  7.         res = []
  9.         while cur:
  10.             for node in cur:
  11.                 if node.left:
  12.                     nexts.append(node.left)
  13.                 if node.right:
  14.                     nexts.append(node.right)
  15.             res.append([child.val for child in cur])
  16.             cur ,nexts = nexts, []
  17.         return res

重建二叉树

根据遍历重建二叉树
https://blog.nowcoder.net/n/13028d6c72c04f53b068271cb51e6074

Morris遍历

如果题目或者面试官告诉我们不能修改树结构，那么Morris遍历是不能使用的。Morris利用了叶节点的大量空闲指针实现遍历，能够实现时间复杂度O(n)，空间复杂度O(1)的遍历，在Morris遍历的基础上我们能改出前、中、后序遍历的结果。

二叉树遍历 - 图3
Morris遍历的步骤：
假设当前来到的节点为cur，开始时来到头节点位置

  • 如果cur没有左子树，cur向右移动（cur.right）
  • 如果cur有左子树，找到左子树上的最右节点mostRight:
    • a. 如果mostRight的右指针为空，让其指向cur，然后cur向左移动（cur = cur.left）
    • b. 如果mostRight的右指针指向cur，让其指向null，然后cur向右移动（cur = cur.right）
  • cur为空时遍历停止

图中树对应的Morris遍历为：1-> 2 -> 4-> 2 -> 5 -> 1 -> 3 ->6 -> 3 -> 7，不难发现，根节点会到达两次，第二次是通过cur的右节点回到的。结合上图我们简单梳理下流程：

  1. 遍历从根节点1出发，此时cur节点是1，mostRight节点是5，且mostRight的右指针指向None，因此我们把5的右指针指向1，cur节点向做左移动，到达2
  2. 此时cur节点是2，mostRight节点是4，且mostRight的右指针指向None，因此我们把4的右指针指向2，cur节点向做左移动，到达4
  3. 此时cur节点是4，mostRight节点是None，cur向右移动，到达2
  4. 此时cur节点是2，mostRight节点是4，且mostRight的右指针指向2，因此我们把4的右指针指向None，cur节点向做右移动，到达5
  5. 此时cur节点是5，mostRight节点是None，cur向右移动，到达1
  6. 此时cur节点是1，mostRight节点是5，且mostRight的右指针指向1，因此我们把5的右指针指向None，cur节点向做右移动，到达3

右子树类似

Morris遍历

  1. class TreeNode(object):
  2.     def __init__(self, val, left = None, right = None):
  3.         self.val = val
  4.         self.left = left
  5.         self.right = right
  8. def morris(root):
  9.     if not root:
  10.         return None
  12.     cur = root
  13.     while cur:
  14.         print(cur.val)
  15.         mostRight = cur.left
  16.         # 有左子树
  17.         if mostRight:
  18.             while mostRight.right and mostRight.right != cur:
  19.                 mostRight = mostRight.right
  21.             # 拿到了左子树的最右节点
  22.             if not mostRight.right:
  23.                 mostRight.right = cur
  24.                 cur = cur.left
  25.                 continue
  26.             else:
  27.                 mostRight.right = None
  28.         cur = cur.right

Morris改前序遍历

  1. def morris_to_preorder(root):
  2.     """
  3.     一个节点只能到达一次 直接打印  一个节点能到达两次 第一次打印
  4.     :return:
  5.     """
  6.     if not root:
  7.         return None
  8.     cur = root
  9.     while cur:
  10.         mostRight = cur.left
  11.         # 有左子树
  12.         if mostRight:
  13.             while mostRight.right and mostRight.right != cur:
  14.                 mostRight = mostRight.right
  16.             # 拿到了左子树的最右节点
  17.             if not mostRight.right:
  18.                 print(cur.val)
  19.                 mostRight.right = cur
  20.                 cur = cur.left
  21.                 continue
  22.             else:
  23.                 mostRight.right = None
  24.         else:
  25.             print(cur.val)
  26.         cur = cur.right

Morris改中序遍历

  1. def morris_to_inorder(root):
  2.     """
  3.     一个节点只能到达一次 直接打印  一个节点能到达两次 第二次打印
  4.     :return:
  5.     """
  6.     if not root:
  7.         return None
  8.     cur = root
  9.     while cur:
  10.         mostRight = cur.left
  11.         # 有左子树
  12.         if mostRight:
  13.             while mostRight.right and mostRight.right != cur:
  14.                 mostRight = mostRight.right
  16.             # 拿到了左子树的最右节点
  17.             if not mostRight.right:
  18.                 mostRight.right = cur
  19.                 cur = cur.left
  20.                 continue
  21.             else:
  22.                 mostRight.right = None
  23.         print(cur.val)
  24.         cur = cur.right

Morris改后序遍历

  1. def morris_to_postorder(root):
  2.     """
  3.     打印时机能放在能回到自己两次的节点
  4.     1 2 4 2 5 1 3 6 3 7
  5.     第二次碰到2时候 逆序打印左子树的右边界 4
  6.     第二次碰到1时候 逆序打印左子树的右边界 5 2
  7.     第二次碰到3时候 逆序打印左子树的有边界 6
  8.     单独打印整棵树的右边界 逆序
  9.     :return:
  10.     """
  11.     # 我们定义两个子方法逆序、打印整棵右子树的右边界
  12.     def reverse_edge(node:TreeNode):
  13.         if not node:
  14.             return None
  15.         pre, cur = None, node
  16.         while cur:
  17.             nexts = cur.right
  18.             cur.right = pre
  19.             pre = cur
  20.             cur = nexts
  21.         return pre
  23.     def printEdge(head: TreeNode):
  24.         tail = reverse_edge(head)
  25.         cur = tail
  26.         while cur:
  27.             print(cur.val)
  28.             cur = cur.right
  29.         reverse_edge(tail)
  31.     if not root:
  32.         return None
  33.     cur = root
  34.     while cur:
  35.         mostRight = cur.left
  36.         # 有左子树
  37.         if mostRight:
  38.             while mostRight.right and mostRight.right != cur:
  39.                 mostRight = mostRight.right
  40.             # 拿到了左子树的最右节点
  41.             if not mostRight.right:
  42.                 mostRight.right = cur
  43.                 cur = cur.left
  44.                 continue
  45.             else:
  46.                 mostRight.right = None
  47.                 printEdge(cur.left) # 逆序打印左树的右边界
  48.         cur = cur.right
  49.     printEdge(root)

测试例子：

  1. root = TreeNode(1)
  2. left = TreeNode(2)
  3. left.left = TreeNode(4)
  4. left.right = TreeNode(5)
  5. right = TreeNode(3)
  6. right.left = TreeNode(6)
  7. right.right = TreeNode(7)
  9. root.left = left
  10. root.right = right
  12. rnt = morris_to_pretorder(root)
  13. # rnt = morris_to_inorder(root)
  14. # rnt = morris_to_postorder(root)