【算法】二叉树遍历算法总结：前序中序后序遍历

本是古典何须时尚 2023-07-07 11:05 56阅读 0赞

![format_png][]

# 前言 #

二叉树遍历是非常经典的算法题，也是二叉树的一道基础算法题。

但是在平常的笔试面试中，其出现的频率其实并不是特别的高，我推测是这种题目相对来说比较基础，算是一个基础知识点。

比如剑指offer中出现的后序遍历题目，是给出一个数字序列，让你判断是不是平衡二叉树后序遍历序列，这样出题的难度比直接让你写后序遍历难很多。

但是，二叉树遍历容易吗？在递归方法下，前中后序遍历都是一个思路，理解起来也比较容易。

**但是只是用迭代的话，二叉树遍历其实是有难度的！**，这也是为什么LeetCode会在这三题题目的下方写出`进阶: 递归算法很简单，你可以通过迭代算法完成吗？`这句话了。

**本文的主要内容如下：**

*  **题目定义**：
    
     *  上篇：二叉树前序、中序、后序遍历
     *  下篇：层序遍历、其他遍历相关题型
 *  **解题思路**：递归 + 迭代+ **莫里斯Morris遍历**
 *  **解题代码**：Java + Python

**注1**：本文中的解题思路会尽量的全面，但是解题方法千变万化，有很多奇技淫巧我不会去介绍，大家有兴趣可以自行扩展学习。

**注2**：本文中的代码会尽量简单，易懂，并不会去追求极致的写法（比如：在一行内完成，使用各种非正式的库等）。

# 正文 #

## 二叉树的定义 ##

最多有两棵子树的树被称为二叉树

![format_png 1][]

二叉树下还有很多种特殊的二叉树，下方简单介绍几种常用的。

### 满二叉树 ###

二叉树中所有非叶子结点的度都是2，且叶子结点都在同一层次上

![format_png 2][]

### 完全二叉树（可以不满） ###

如果一个二叉树与满二叉树前m个节点的结构相同，这样的二叉树被称为完全二叉树。也就是说，如果把满二叉树从右至左、从下往上删除一些节点，剩余的结构就构成完全二叉树。

![format_png 3][]

### 二叉搜索树 ###

二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：

*  若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 *  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 *  它的左、右子树也分别为二叉排序树

![format_png 4][]

## 二叉树前中后序遍历 ##

### 遍历方法 ###

前序遍历：根结点 —> 左子树 —> 右子树

中序遍历：左子树—> 根结点 —> 右子树

后序遍历：左子树 —> 右子树 —> 根结点

### 题目介绍 ###

#### 前序遍历 ####

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入栈，如果有左孩子，依次入栈，那么入栈顺序为：1，2，4。由于4的左子树为空，停止入栈，此时栈为\{1，2，4\}。
2.  此时将4出栈，并遍历4，由于4也没有右孩子，那么根据中序遍历的规则，我们显然应该继续遍历4的父亲2，情况是这样。所以我们继续将2出栈并遍历2，2存在右孩子，将5入栈，此时栈为\{1，5\}。
3.  5没有孩子，则将5出栈并遍历5，这也符合中序遍历的规则。此时栈为\{1\}。
4.  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。
> 
> 1.  如果当前节点的左孩子为空，则将其右孩子作为当前节点。
> 2.  如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
>     
>     a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
>     
>     b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。倒序输出从当前节点的左孩子到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右孩子。
> 3.  重复以上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][qqxx6661]
 *  CSDN：[@Rude3knife][Rude3knife]
 *  知乎：[@后端技术漫谈][Link 1]
 *  简书：[@蛮三刀把刀][Link 2]
 *  掘金：[@蛮三刀把刀][Link 3]

### 原创博客主要内容 ###

*  后端开发相关技术文章
 *  Java面试知识点复习全手册
 *  设计模式/数据结构
 *  LeetCode/剑指offer 算法题解析
 *  SpringBoot/SpringCloud菜鸟入门实战系列
 *  爬虫相关技术文章
 *  逸闻趣事/好书分享/个人生活

### 个人公众号：后端技术漫谈 ###

![公众号：后端技术漫谈.jpg][.jpg]

**如果文章对你有帮助，不妨收藏，投币，转发，在看起来~**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAyMC8yLzIyLzE3MDZjNGI5NDBiNTE1MDQ?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAyMC8yLzIyLzE3MDZjNGMxMTMxNmU4ZWU?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAyMC8yLzIyLzE3MDZjNGMyODEzMmJiMDU?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAyMC8yLzIyLzE3MDZjNGNiYTM5MDAzYmM?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAyMC8yLzIyLzE3MDZjNGNkMjM2MjMyNTE?x-oss-process=image/format,png
[qqxx6661]: https://github.com/qqxx6661
[Rude3knife]: http://blog.csdn.net/qqxx6661
[Link 1]: https://www.zhihu.com/people/yang-zhen-dong-1/
[Link 2]: https://www.jianshu.com/u/b5f225ca2376
[Link 3]: https://juejin.im/user/5b48015ce51d45191462ba55
[.jpg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAyMC8yLzIyLzE3MDZjNGJhNGEyYzM2YTc?x-oss-process=image/format,png