【算法】二叉树遍历算法总结：前序中序后序遍历
- 2020 年 2 月 26 日
- 筆記
前言
二叉树遍历是非常经典的算法题，也是二叉树的一道基础算法题。
但是在平常的笔试面试中，其出现的频率其实并不是特别的高，我推测是这种题目相对来说比较基础，算是一个基础知识点。
比如剑指offer中出现的后序遍历题目，是给出一个数字序列，让你判断是不是平衡二叉树后序遍历序列，这样出题的难度比直接让你写后序遍历难很多。
但是，二叉树遍历容易吗？在递归方法下，前中后序遍历都是一个思路，理解起来也比较容易。
但是只是用迭代的话，二叉树遍历其实是有难度的！，这也是为什么LeetCode会在这三题题目的下方写出进阶: 递归算法很简单，你可以通过迭代算法完成吗？这句话了。
本文的主要内容如下：
- 题目定义：
- 上篇：二叉树前序、中序、后序遍历
- 下篇：层序遍历、其他遍历相关题型
- 解题思路：递归 + 迭代+ 莫里斯Morris遍历
- 解题代码：Java + Python
注1：本文中的解题思路会尽量的全面，但是解题方法千变万化，有很多奇技淫巧我不会去介绍，大家有兴趣可以自行扩展学习。
注2：本文中的代码会尽量简单，易懂，并不会去追求极致的写法（比如：在一行内完成，使用各种非正式的库等）。
正文
二叉树的定义
最多有两棵子树的树被称为二叉树
二叉树下还有很多种特殊的二叉树，下方简单介绍几种常用的。
满二叉树
二叉树中所有非叶子结点的度都是2，且叶子结点都在同一层次上
完全二叉树（可以不满）
如果一个二叉树与满二叉树前m个节点的结构相同，这样的二叉树被称为完全二叉树。也就是说，如果把满二叉树从右至左、从下往上删除一些节点，剩余的结构就构成完全二叉树。
二叉搜索树
二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
二叉树前中后序遍历
遍历方法
前序遍历：根结点 —> 左子树 —> 右子树
中序遍历：左子树—> 根结点 —> 右子树
后序遍历：左子树 —> 右子树 —> 根结点
题目介绍
前序遍历
LeetCode题目地址：
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
输入: [1,null,2,3] 1 2 / 3 输出: [1,2,3]
中序遍历
LeetCode题目地址：
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
输入: [1,null,2,3] 1 2 / 3 输出: [1,3,2]
后序遍历
LeetCode题目地址：
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
输入: [1,null,2,3] 1 2 / 3 输出: [3,2,1]
解题思路详解与代码实现
二叉树的前中后序遍历，主要就是两种思路，一种是递归，一种是迭代。
如果看到这里还没有感觉，不用担心，先直接往下看，第一个代码（前序遍历的递归思路）会帮助你提升感觉。
递归思路
递归思路是最容易理解的思路，并且前中后序遍历都相同。
比如前序遍历，在递归的函数里，先往结果数组里加入根节点，然后加入根节点的左节点，然后加入根节点的右节点。最后所有递归的函数运行完毕，结果集就已经完成了。
中序和后序的思路相同，就不再赘述了。
前序遍历
Java：
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } preorder(root, result); return result; } private static List<Integer> preorder(TreeNode root, List<Integer> result) { if (root != null) { result.add(root.val); preorder(root.left, result); preorder(root.right, result); } return result; } }
Python：
class Solution(object): def _preorderTraversal(self, root, result): if root: result.append(root.val) self._preorderTraversal(root.left, result) self._preorderTraversal(root.right, result) def preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root == None: return [] result = [] self._preorderTraversal(root, result) return result
中序遍历
Java：
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } result = inorder(root, result); return result; } private static List<Integer> inorder(TreeNode root, List<Integer> result) { if (root != null) { inorder(root.left, result); result.add(root.val); inorder(root.right, result); } return result; } }
Python：
class Solution(object): def generate(self, root, result): if root: self.inorder(root.left, list) result.append(root.val) self.inorder(root.right, list) def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root: return [] result = [] self.generate(root, result) return result
后序遍历
Java：
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } result = postorder(root, result); return result; } private static List<Integer> postorder(TreeNode root, List<Integer> result) { if (root != null) { postorder(root.left, result); postorder(root.right, result); result.add(root.val); } return result; } }
Python：
class Solution(object): def _postorderTraversal(self, root, result): if root: self._postorderTraversal(root.left, result) self._postorderTraversal(root.right, result) result.append(root.val) def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root == None: return [] result = [] self._postorderTraversal(root, result) return result
迭代思路
前序遍历
我们需要一个栈来完成遍历。
1.根节点入栈 2.取出节点，值加入结果，然后先加右，后加左。 3.重复2
这样就得到了 根节点——左子树——右子树 的遍历结果集。
Java：
来自官方题解
LinkedList<TreeNode> stack = new LinkedList<>(); LinkedList<Integer> output = new LinkedList<>(); if (root == null) { return output; } stack.add(root); while (!stack.isEmpty()) { TreeNode node = stack.pollLast(); output.add(node.val); if (node.right != null) { stack.add(node.right); } if (node.left != null) { stack.add(node.left); } } return output; }
Python：
class Solution(object): def preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ ret = [] stack = [root] while stack: node = stack.pop() if node: ret.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return ret
中序遍历
还是使用一个栈来解决问题。
步骤如下：
1 / 2 3 / / 4 5 6 7
- 我们将根节点1入栈，如果有左孩子，依次入栈，那么入栈顺序为：1，2，4。由于4的左子树为空，停止入栈，此时栈为{1，2，4}。
- 此时将4出栈，并遍历4，由于4也没有右孩子，那么根据中序遍历的规则，我们显然应该继续遍历4的父亲2，情况是这样。所以我们继续将2出栈并遍历2，2存在右孩子，将5入栈，此时栈为{1，5}。
- 5没有孩子，则将5出栈并遍历5，这也符合中序遍历的规则。此时栈为{1}。
- 1有右孩子，则将1出栈并遍历1，然后将右孩子3入栈，并继续以上三个步骤即可。
栈的变化过程：{1}->{1,2}->{1,2,4}->{1,2}->{1}->{1,5}->{1}->{}->{3}->{3,6}->{3}->{}->{7}->{}。
总结：从根节点遍历，先放入所有有左孩子的节点直到没有，然后出栈，出栈的时候就将出栈的数字放入结果集，然后看其有没有右孩子，有的话右孩子入栈。
Java：
官方题解
public class Solution { public List <Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); res.add(curr.val); curr = curr.right; } return res; } }
Python：
class Solution: # @param root, a tree node # @return a list of integers def inorderTraversal(self, root): result = [] stack = [] while root or stack: if root: stack.append(root) root = root.left else: root = stack.pop() result.append(root.val) root = root.right return result
后序遍历
将数组输出为右子树-左子树-根节点。最后，再将数组倒序输出，形成后序遍历。这样代码并不用很繁琐，也能做完迭代。
是不是似曾相识，没错，和前序遍历的迭代几乎一样，仅仅是先放右节点再放左节点变成了先放左节点再放右节点，然后倒序输出。
Java：
class Solution { public List<Integer> postorderTraversal(TreeNode root) { LinkedList<TreeNode> stack = new LinkedList<>(); LinkedList<Integer> output = new LinkedList<>(); if (root == null) { return output; } stack.add(root); while (!stack.isEmpty()) { TreeNode node = stack.pollLast(); output.addFirst(node.val); if (node.left != null) { stack.add(node.left); } if (node.right != null) { stack.add(node.right); } } return output; } }
Python：
class Solution(object): def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root is None: return [] ret = [] stack = [root] while stack: node = stack.pop() if node: ret.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return ret[::-1]
所以迭代方式，前后序是非常类似的，中序遍历可能需要单独理解下。
莫里斯遍历
二叉树常规的遍历方法是用递归来实现的，这种方法一般都需要O(n)的空间复杂度和O(n)的时间复杂度。而Morris方法实现的是O(1)的空间复杂度和O(n)的时间复杂度。 我们知道，遍历二叉树时，最大的难点在于，遍历到子节点的时候怎样重新返回到父节点（假设节点中没有指向父节点的p指针），由于不能用栈作为辅助空间。(不然就是普通迭代方法)。
为了解决这个问题，Morris方法用到了线索二叉树（threaded binary tree）的概念。在Morris方法中不需要为每个节点额外分配指针指向其前驱（predecessor）和后继节点（successor），只需要利用叶子节点中的左右空指针指向某种顺序遍历下的前驱节点或后继节点就可以了。
听不懂没关系，下面使用中序遍历作为例子来理解莫里斯遍历到底是什么意思，例子来自LeetCode官方题解：
中序遍历
Step 1: 将当前节点current初始化为根节点 Step 2: While current不为空， 若current没有左子节点 a. 将current添加到输出 b. 进入右子树，亦即, current = current.right 否则 a. 在current的左子树中，令current成为最右侧节点的右子节点 b. 进入左子树，亦即，current = current.left
1 / 2 3 / / 4 5 6
首先，1 是根节点，所以将 current 初始化为 1。1 有左子节点 2，current 的左子树是
2 / 4 5
在此左子树中最右侧的节点是 5，于是将 current(1) 作为 5 的右子节点。令 current = cuurent.left (current = 2)。现在二叉树的形状为:
2 / 4 5 1 3 / 6
对于 current(2)，其左子节点为4，我们可以继续上述过程
4 2 5 1 3 / 6
Java：
class Solution { public List < Integer > inorderTraversal(TreeNode root) { List < Integer > res = new ArrayList < > (); TreeNode curr = root; TreeNode pre; while (curr != null) { if (curr.left == null) { res.add(curr.val); curr = curr.right; // move to next right node } else { // has a left subtree pre = curr.left; while (pre.right != null) { // find rightmost pre = pre.right; } pre.right = curr; // put cur after the pre node TreeNode temp = curr; // store cur node curr = curr.left; // move cur to the top of the new tree temp.left = null; // original cur left be null, avoid infinite loops } } return res; } }
前序遍历
理解了中序遍历，前序和后序遍历相对来说也就更容易理解了。所以前序和后序贴了思路，代码我也没自己写后submit，在这里就不放了。
算法的思路是从当前节点向下访问先序遍历的前驱节点，每个前驱节点都恰好被访问两次。 首先从当前节点开始，向左孩子走一步然后沿着右孩子一直向下访问，直到到达一个叶子节点（当前节点的中序遍历前驱节点），所以我们更新输出并建立一条伪边 predecessor.right = root 更新这个前驱的下一个点。如果我们第二次访问到前驱节点，由于已经指向了当前节点，我们移除伪边并移动到下一个顶点。
后序遍历
后续遍历稍显复杂，需要建立一个临时节点dump，令其左孩子是root。并且还需要一个子过程，就是倒序输出某两个节点之间路径上的各个节点。 步骤： 当前节点设置为临时节点dump。
- 如果当前节点的左孩子为空，则将其右孩子作为当前节点。
- 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。 a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。 b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。倒序输出从当前节点的左孩子到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右孩子。
- 重复以上1、2直到当前节点为空。
参考
- https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
- https://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html
- https://blog.csdn.net/softwarex4/article/details/95986102
关注我
我是一名后端开发工程师。
主要关注后端开发，数据安全，爬虫，物联网，边缘计算等方向，欢迎交流。
各大平台都可以找到我
- 微信公众号：后端技术漫谈
- Github：@qqxx6661
- CSDN：@Rude3knife
- 知乎：@后端技术漫谈
- 简书：@蛮三刀把刀
- 掘金：@蛮三刀把刀
原创博客主要内容
- 后端开发相关技术文章
- Java面试知识点复习全手册
- 设计模式/数据结构
- LeetCode/剑指offer 算法题解析
- SpringBoot/SpringCloud菜鸟入门实战系列
- 爬虫相关技术文章
- 逸闻趣事/好书分享/个人生活
