二叉树遍历，在面试中出现的概率极大，常常需要面试者掌握二叉树的三种遍历方式，前序遍历、中序遍历、后序遍历，同时又要要求面试者掌握递归和非递归实现。

前序遍历、中序遍历、后序遍历三个遍历中，递归的实现方式最简单，而且有规律可循。
三种变量的非递归实现较难。

三个遍历方式的定义分别是：

  • 前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树
  • 中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树
  • 后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点


Tip：以根节点的访问顺序作为前中后遍历的定义，且三种遍历方式都是先遍历左子树，再遍历右子树。**

本节将会教你用一套模板实现三种递归方式，面试不再愁！！！

前序遍历

递归

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     def preorderTraversal(self, root: TreeNode) -> List[int]:
  10.         if not root:
  11.             return []
  12.         return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

非递归

  • 模板法

先记住先序遍历，中序和后序遍历只需要在此基础上修改即可

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     def preorderTraversal(self, root: TreeNode) -> List[int]:
  10.         if root is None: 
  11.             return []
  12.         result = [] # 保存结果
  13.         stack = [root] # 压入 root 节点
  14.         while stack:
  15.             p = stack.pop() # 访问过的节点弹出
  16.             if p is None: # 空节点表示之前已经访问过了，现在需要处理除了递归之外的内容
  17.                 p = stack.pop() # 彻底从栈中移除
  18.                 result.append(p.val)
  19.             else:
  20.                 if p.right:  # 右节点先压栈，最后处理
  21.                     stack.append(p.right)  
  22.                 if p.left: 
  23.                     stack.append(p.left)
  24.                 stack.append(p) # 当前节点重新压栈（留着以后处理），因为先序遍历所以最后压栈
  25.                 stack.append(None) # 在当前节点之前加入一个空节点表示已经访问过了
  26.         return result
  • 非模板

前序遍历的非递归实现比较简单
建立一个栈 stack，先把 root 节点压入，然后 while 判断 stack 是否为空作为循环退出的条件
进入 while 循环以后，弹出栈顶的节点，若该节点有右子节点、左子节点的话，压入栈中（注意：压入栈的时候先压入右子节点，再压入左子节点，这是因为栈是后入先出，左子节点最后被压入，但是最先被弹出）

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     def preorderTraversal(self, root: TreeNode) -> List[int]:
  10.         if not root:
  11.             return []
  12.         stack = [root]
  13.         result = []
  14.         while stack:
  15.             node = stack.pop()
  16.             if node:
  17.                 result.append(node.val)
  18.                 if node.right:
  19.                     stack.append(node.right) # 先压入右边
  20.                 if node.left:
  21.                     stack.append(node.left) # 后压入左边
  22.         return result

中序遍历

递归

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     def inorderTraversal(self, root: TreeNode) -> List[int]:
  10.         if not root:
  11.             return []
  12.         return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

时间复杂度：O(n)。
空间复杂度：最坏情况下需要空间O(n)，平均情况为 O(logn)。

非递归

  • 模板法 ```python

    Definition for a binary tree node.

    class TreeNode:

    def init(self, x):

    self.val = x

    self.left = None

    self.right = None

class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: if root is None: return [] result = [] stack = [root] while stack: p = stack.pop() if p is None: p = stack.pop() result.append(p.val) else: if p.right: # 先压入右边 stack.append(p.right) stack.append(p) stack.append(None) if p.left: stack.append(p.left) return result

  2. - 非模板
  3. > 创建一个栈 stack，一个 cur 变量，用来记录当前的节点，把 cur 或 stack 非空作为循环的条件，进入循环，判断 cur 节点是否为空，非空的话，往复变量 当前节点的左子节点，压入栈中。
  5. ```python
  6. # Definition for a binary tree node.
  7. # class TreeNode:
  8. #     def __init__(self, x):
  9. #         self.val = x
  10. #         self.left = None
  11. #         self.right = None
  13. class Solution:
  14.     def inorderTraversal(self, root: TreeNode) -> List[int]:
  15.         if not root:
  16.             return []
  17.         stack = [] # 最开始不压入 root 节点
  18.         result = []
  19.         cur = root # 
  20.         while cur or stack: # 或
  21.             while cur:  # 不断把当前节点的 左子节点压入
  22.                 stack.append(cur)
  23.                 cur = cur.left
  24.             cur = stack.pop() # 弹出
  25.             result.append(cur.val)
  26.             cur = cur.right
  27.         return result

后序遍历

递归

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     def postorderTraversal(self, root: TreeNode) -> List[int]:
  10.         if not root:
  11.             return []
  12.         return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

非递归

  • 模板法 ```python

    Definition for a binary tree node.

    class TreeNode:

    def init(self, x):

    self.val = x

    self.left = None

    self.right = None

class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: if root is None: return [] result = [] stack = [root] while stack: p = stack.pop() if p is None: p = stack.pop() result.append(p.val) else: stack.append(p) stack.append(None) if p.right: stack.append(p.right) if p.left: stack.append(p.left) return result

  2. - 非模板<br />
  3. > 后序遍历弹出（输出值）的条件是**当前节点是叶节点或者子节点也访问过了**
  5. ```python
  6. # Definition for a binary tree node.
  7. # class TreeNode:
  8. #     def __init__(self, x):
  9. #         self.val = x
  10. #         self.left = None
  11. #         self.right = None
  13. class Solution:
  14.     def postorderTraversal(self, root: TreeNode) -> List[int]:
  15.         if not root:
  16.             return []
  17.         stack = [root]
  18.         result = []
  19.         p = root
  20.         while stack:
  21.             top = stack[-1]
  22.             # 如果是叶子结点，儿子也已经有访问过，则输出它，并记录下当前输出结点
  23.             if (top.left == p) or (top.right == p) or \
  24.                     (not top.left and not top.right): # 叶子元素
  25.                 p = stack.pop()
  26.                 result.append(p.val)
  27.             # 如果它不是叶子结点，儿子也没有访问，那么就需要将它的右儿子，左儿子压入。 
  28.             else:
  29.                 # 先访问的后加入
  30.                 if top.right: # 先加右
  31.                     stack.append(top.right)
  32.                 if top.left: # 再加左
  33.                     stack.append(top.left)
  34.         return result

口诀

创建 result 保存结果
创建 stack 压入 root
while 循环判断 stack
首先 p=stack.pop()
p 为空，p=stack.pop()，result.append(p.val)
p 非空，按照题意压 p, p.right, p.left
压入 p 之后压入 None，标记已经被访问

参考