【面试小知识】带你深入了解二叉树的前中序遍历

太过爱你忘了你带给我的痛 2023-03-04 08:23 19阅读 0赞

> ☞梦想进大厂的一只程序猿☜
> 
> ☞期望毕业前力扣刷够400题☜
> 
> ☞正在复习数据结构和算法☜
> 
> ☞博客地址：[https://www.huangliangshuai.com/][https_www.huangliangshuai.com]☜

# 引言 #

本文主要讲述关于二叉树的四种遍历：前序、中序、后序、层次遍历，其中前序、中序、后序分别以递归和迭代的两种解法去讲解

#  #

# 二叉树的前序遍历 #

作为二叉树的前序遍历，我们先来看看下面这棵二叉树：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70][]

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

所以，这棵二叉树，他的前序遍历为：ABDGECF

用递归的思维写，相信大家都会，下面是代码：

public class Tree {
    	List<Integer> list = new ArrayList<Integer>();
    
    	public List<Integer> preorderTraversal(TreeNode root) {
    		if (root != null) {
    			list.add(root.val);
    			preorderTraversal(root.left);
    			preorderTraversal(root.right);
    		}
    		return list;
    	}
    }

重点讲解一下关于前序遍历迭代的思想：**利用栈(Stack)来实现**

先看看代码：

public List<Integer> preorderTraversal(TreeNode root) {
    		Stack<TreeNode> stack = new Stack<TreeNode>();// 保存结果
    		List<Integer> list = new ArrayList<Integer>();// 调用栈
    		if (root != null) {
    			stack.push(root); // 首先介入root节点
    		}
    		while (!stack.isEmpty()) {
    			TreeNode tempNode = stack.pop();// 访问过的节点弹出
    			if (tempNode != null) {
    				if (tempNode.right != null)
    					stack.push(tempNode.right);// 右节点先压栈，最后处理
    				if (tempNode.left != null)
    					stack.push(tempNode.left);
    				stack.push(tempNode);// 当前节点重新压栈（留着以后处理），因为先序遍历所以最后压栈
    				stack.push(null);// 在当前节点之前加入一个空节点表示已经访问过了
    			} else {
    				list.add(stack.pop().val); // stack.pop()是null之前压栈的一个节点，也就是上面stack.push(tempNode)中的那个tempNode
    			}
    		}
    		return list;
    	}

相信看了代码后，大部分人脑袋中有个印象吧。按照上面的二叉树图，带领大家分析一下：

首先将A入栈，然后A出栈(用tempNode获取A的值)，将C、B入栈，将A再次入栈，将null入栈，代表当前tempNode已经被访问过

![20200802204404689.png][]

如上，我们再一次进行循环时，会碰到null，这时候会把A弹到list中，接着以B进行新一轮的循环，如下:

![20200802213153677.png][]

碰到null，弹出B至list，继续往下，以D进行新一轮的循环，入栈G

![20200802213057224.png][]

按照上述做法，依次弹出D、G、E ，将C弹出的时候，还是会实行上述方法，最后得到：ABDGECF

# 二叉树的中序遍历 #

作为二叉树的后序遍历，我们先来看看下面这棵二叉树：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70][]

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

所以，这棵二叉树，他的中序遍历为：GDBEACF

用递归的思维写，相信大家都会，下面是代码：

public class Tree {
    	List<Integer> list = new ArrayList<Integer>();
    
    	public List<Integer> intermediateOrderTraversal(TreeNode root) {
    		if (root != null) {
    			intermediateOrderTraversal(root.left);
    			list.add(root.val);
    			intermediateOrderTraversal(root.right);
    		}
    		return list;
    	}
    }

我们来看看迭代的方法，下面是代码：

public class tree {
    	public List<Integer> intermediateOrderTraversal(TreeNode root) {
    		Stack<TreeNode> stack = new Stack<TreeNode>();// 保存结果
    		List<Integer> list = new ArrayList<Integer>();// 调用栈
    		if (root != null) {
    			stack.push(root); // 首先介入root节点
    		}
    		while (!stack.isEmpty()) {
    			TreeNode tempNode = stack.pop();// 访问过的节点弹出
    			if (tempNode != null) {
    				if (tempNode.right != null)
    					stack.push(tempNode.right);// 右节点先压栈，最后处理
    				stack.push(tempNode);// 当前节点重新压栈（留着以后处理），因为先序遍历所以最后压栈
    				stack.push(null);// 在当前节点之前加入一个空节点表示已经访问过了
    				if (tempNode.left != null)
    					stack.push(tempNode.left);
    			} else {
    				list.add(stack.pop().val); // stack.pop()是null之前压栈的一个节点，也就是上面stack.push(tempNode)中的那个tempNode
    			}
    		}
    		return list;
    	}
    }

大家有没有感觉这个代码有点眼熟，对，他和我们的前序遍历迭代代码基本没有差距，只是替换了代码之间的位置，我们一起来分析一下这一段代码：

首先，也是将root(A)入栈，出栈，判断其右子树C入栈，将弹出的A入栈，加null（代表被访问过），将左子树B入栈，如下所示：

![20200802214707854.png][]

我们以B为起点，再一次进行循环，得到：

![20200802215058716.png][]

以D为起点，再一次进行循环，得到：

![20200802220757895.png][]

到这一步，开始我们的输出list了，首先是从栈中取出G，查找G的右子树->null，然后将G入栈，null入栈，输出G、D等

到这，可能有的人会迷惑，为什么要用null来进行分隔呢？

我们不分隔不可以吗？

假设我们不分隔的话，如下图所示：

![20200803133527902.png][]

我们可以想想，什么条件下我们选择输出它呢？也就是当到达什么程度时，我们选择输出，有的人可能会说，当我当前的root点左右子树都为空的时候选择输出它，可是我们仅仅能判断出G，到D的时候怎么判断，根据栈吗？

你要知道，面试的时候，一道题的时间不会超过20分钟，假如你按这种方式，在心中过一遍，只要掌握了前序，你就掌握了中序、后序，何乐而不为呢？

与其纠结生活，不如沉浸生活。

# 二叉树的后序遍历 #

作为二叉树的后序遍历，我们先来看看下面这棵二叉树：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70][]

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

所以，这棵二叉树，他的后序遍历：GDEBFCA

用递归的思维写，相信大家都会，下面是代码：

public class Tree {
    	List<Integer> list = new ArrayList<Integer>();
    
    	public List<Integer> afterTheOrder(TreeNode root) {
    		if (root != null) {
    			afterTheOrder(root.left);
    			afterTheOrder(root.right);
    			list.add(root.val);
    		}
    		return list;
    	}
    }

我们来看看迭代的方法：

public class tree {
    
    	public List<Integer> postorderTraversal(TreeNode root) {
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		List<Integer> list = new ArrayList<Integer>();
    		if (root == null) {
    			return list;
    		}
    		stack.push(root);
    		while (!stack.isEmpty()) {
    			TreeNode tempNode = stack.pop();
    			if (tempNode != null) {
    				stack.push(tempNode);
    				stack.push(null);
    				if (tempNode.right != null) {
    					stack.push(tempNode.right);
    				}
    				if (tempNode.left != null) {
    					stack.push(tempNode.left);
    				}
    			} else {
    				list.add(stack.pop().val);
    			}
    		}
    		return list;
    	}
    }

具体的逻辑，可以按照上述的走法，自己跑跑，对于层次的各种遍历和根据前序、中序、后序求原二叉树将会在以后的地方讲解。

可爱的读者，点个关注吧！

[https_www.huangliangshuai.com]: https://www.huangliangshuai.com/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20230208/ac3b9425c0414108afec85d2374adf59.png
[20200802204404689.png]: /images/20230208/a9aa4988554b4b368a3e7fced07561fe.png
[20200802213153677.png]: /images/20230208/e115f01913a3403f91968a1882d3ec94.png
[20200802213057224.png]: /images/20230208/3007298d93f74610bf0c61b4b9e9db3d.png
[20200802214707854.png]: /images/20230208/9e6bbec628514aaf9d0539a4cad8c265.png
[20200802215058716.png]: /images/20230208/cb49ead9215444e3ba41059b6ebdbf31.png
[20200802220757895.png]: /images/20230208/42c6bac998934568a07c7de85f5bc48b.png
[20200803133527902.png]: /images/20230208/87ec44b44c9c4bba9792820c270179d3.png