二叉树的前中后序遍历，递归法，迭代法

￡神魔★判官ぃ 2023-09-27 14:08 21阅读 0赞

## 基础知识： ##

### 1.二叉树深度优先遍历 ###

> ![995341bca6a742d997b423498ba021b4.png][]
> 
> 遍历结果：
> 
> 前序遍历（中左右）：5 4 1 2 6 7 8  
> 中序遍历（左中右）：1 4 2 5 7 6 8  
> 后序遍历（左右中）：1 2 4 7 8 6 5

### 2.递归法 ###

> #### 确定递归函数的参数和返回值： ####
> 
> 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
> 
> #### 确定终止条件： ####
> 
> 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
> 
> #### 确定单层递归的逻辑： ####
> 
> 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程

### 3.迭代法 ###

> 为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？
> 
> 迭代的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
> 
> 一般需要使用栈来辅助实现

## 前中后序 遍历的实现 ##

### 一、前序遍历 ###

#### 1.递归 ####

> 思路：
> 
> 我们只要首先将 root 节点的值加入数组，然后递归调用 preorder(root.left) 来遍历 root 节点的左子树，最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可。
> 
> 递归终止的条件：碰到空节点。（root == null）
> 
> 代码实现：
> 
>     public List<Integer> preorderTraversal(TreeNode root) {
>     //创建数组来存储遍历结果
>             List<Integer> res = new ArrayList<Integer>();
>     //调用递归方法
>             preorder(root, res);
>             return res;
>         }
>     
>         public void preorder(TreeNode root, List<Integer> res) {
>     //终止条件
>             if (root == null) {
>                 return;
>             }
>     //将根节点放入数组
>             res.add(root.val);
>     //递归遍历左子树
>             preorder(root.left, res);
>     //递归遍历右子树
>             preorder(root.right, res);
>         }
> 
> 复杂度分析
> 
> 时间复杂度：O(n)，其中 n 是二叉树的节点数，每一个节点恰好被访问一次。
> 
> 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(log n)，最坏情况下树呈现链状（单分支树），为 O(n)。

#### 2.迭代 ####

> 实现思路：
> 
> 用一个栈来模拟递归的过程实现
> 
> ![a4f473da8a5846bc8398f20675131f50.png][]
> 
> 代码实现：
> 
>     public List<Integer> preorderTraversal(TreeNode root) {
>              //创建一个数组来存放遍历后的值
>             List<Integer> res = new ArrayList<Integer>();
>             //判断根节点
>             if (root == null) {
>                 return res;
>             }
>            //创建辅助栈
>             Deque<TreeNode> stack = new LinkedList<TreeNode>();
>             TreeNode node = root;
>             while (!stack.isEmpty() || node != null) {
>                 //如果node的左右结点都为空，找到叶子结点了
>                 while (node != null) {
>                     //根节点入数组，入栈
>                     res.add(node.val);
>                     stack.push(node);
>                   // 根节点 向左子树移动
>                     node = node.left;
>                 }
>                 //将目前栈顶元素作为根节点
>                 node = stack.pop();
>                 //root向右子树移动
>                 node = node.right;
>             }
>             return res;
>         }
> 
> 时间复杂度：O(n)，其中 nn 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
> 
> 空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状（单分支二叉树），为 O(n)。

### 中序遍历 ###

#### 1.递归法 ####

> 与前序遍历相同，只改变递归遍历的顺序为：左根右
> 
>     public List<Integer> postorderTraversal(TreeNode root) {
>             List<Integer> res = new ArrayList<Integer>();
>             postorder(root, res);
>             return res;
>         }
>     
>         public void postorder(TreeNode root, List<Integer> res) {
>             if (root == null) {
>                 return;
>             }
>             postorder(root.left, res);
>             res.add(root.val);
>             postorder(root.right, res);
>             
>         }
> 
> 时间复杂度：O(n)O(n)  
> 空间复杂度：O(h)O(h)，hh 是树的高度

#### 2.迭代法 ####

> 用一个栈来模拟递归的过程实现
> 
> ![fdcc7f09a9558a9b4e311b0a4b31c1a3.gif][]
> 
>     public List<Integer> inorderTraversal(TreeNode root) {
>     		List<Integer> res = new ArrayList<Integer>();
>             //辅助栈
>     		Stack<TreeNode> stack = new Stack<TreeNode>();
>     		while(stack.size()>0 || root!=null) {
>     			//不断往左子树方向走，每走一次就将当前节点保存到栈中
>     			//这是模拟递归的调用
>     			if(root!=null) {
>     				stack.add(root);
>     				root = root.left;
>     			//当前节点为空，说明左边走到头了，从栈中弹出节点并保存
>     			//然后转向右边节点，继续上面整个过程
>     			} else {
>     				TreeNode tmp = stack.pop();
>     				res.add(tmp.val);
>     				root = tmp.right;
>     			}
>     		}
>     		return res;
>     	}
> 
> 复杂度分析
> 
> 时间复杂度：O(n)，其中 nn 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
> 
> 空间复杂度：O(n)。空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n)的级别。

### 后序遍历 ###

#### 1.递归法： ####

> 与前序遍历相同，只改变递归遍历的顺序为：左右根
> 
>     public List<Integer> postorderTraversal(TreeNode root) {
>             List<Integer> res = new ArrayList<Integer>();
>             postorder(root, res);
>             return res;
>         }
>     
>         public void postorder(TreeNode root, List<Integer> res) {
>             if (root == null) {
>                 return;
>             }
>             postorder(root.left, res);
>             postorder(root.right, res);
>             res.add(root.val);
>         }
> 
> 时间复杂度：O(n)，其中 nn 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
> 
> 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)

#### 2.迭代 ####

> 同样使用栈，和数组，但是因为后序遍历是 ：左 右 根，最先入栈的不是根节点，所以需要一个指针prev先遍历，找到最先入数组的叶子结点。
> 
> 步骤：
> 
> 1.  每拿到一个 节点 就把它保存在 栈 中
> 2.  继续对这个节点的 左子树 重复 过程1，直到左子树为 空
> 3.  因为保存在 栈 中的节点都遍历了 左子树 但是没有遍历 右子树，所以对栈中节点 出栈 并对它的 右子树 重复 过程1
> 4.  直到遍历完所有节点
> 
> 代码实现：
> 
>     public List<Integer> postorderTraversal(TreeNode root) {
>             List<Integer> res = new ArrayList<Integer>();
>             if (root == null) {
>                 return res;
>             }
>             Deque<TreeNode> stack = new LinkedList<TreeNode>();
>             //用一个指针去遍历找到目标结点
>             TreeNode prev = null;
>             while (root != null || !stack.isEmpty()) {
>                 //把左子树的所有左节点入栈
>                 while (root != null) {
>                     stack.push(root);
>                     root = root.left;
>                 }
>                 //找到叶子节点后对该节点进行操作
>                 root = stack.pop();   //将叶子结点出栈，并作为新的根节点，进行以下操作
>                 if (root.right == null || root.right == prev) {
>                     //入数组
>                     res.add(root.val);
>                     prev = root;
>                     root = null;
>                 } else {
>                     //入栈，将右子树置为根，再次循环判断
>                     stack.push(root);
>                     root = root.right;
>                 }
>             }
>             return res;
>         }
> 
> 复杂度分析
> 
> 时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
> 
> 空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

声明：本文部分图片来源于网络，如有侵权亲联系我删除

[995341bca6a742d997b423498ba021b4.png]: https://img-blog.csdnimg.cn/995341bca6a742d997b423498ba021b4.png
[a4f473da8a5846bc8398f20675131f50.png]: https://img-blog.csdnimg.cn/a4f473da8a5846bc8398f20675131f50.png
[fdcc7f09a9558a9b4e311b0a4b31c1a3.gif]: https://img-blog.csdnimg.cn/img_convert/fdcc7f09a9558a9b4e311b0a4b31c1a3.gif