【Java数据结构】二叉树进阶——非递归实现前中后序遍历二叉树+进阶大厂面试题
🗽非递归实现遍历二叉树（深入理解二叉树）
⭐非递归前序遍历
⭐非递归中序遍历
⭐非递归后序遍历
🗽大厂OJ面试题
🎄1. 二叉树的构建及遍历
🎄2. 二叉树的分层遍历
🎄3. 给定一个二叉树，找到该树中两个指定节点的最近公共祖先
🎄4. 二叉树搜索树转换成排序双向链表
🎄5. 根据一棵树的前序遍历与中序遍历构造二叉树
🎄6. 根据一棵树的中序遍历和后序遍历构造二叉树
🎄7. 二叉树创建字符串
🗽非递归实现遍历二叉树（深入理解二叉树）
代码每行都有注释，可以一步一步的画着图走一走，多走几遍，理解会上一个档次！
前序遍历和中序遍历都用到栈，代码可以说一模一样，只不过打印节点的时机不一样
⭐非递归前序遍历
⭐非递归中序遍历
⭐非递归后序遍历
🗽大厂OJ面试题
🎄1. 二叉树的构建及遍历
题目：
思路：
- 本题思路很简单，就是遍历字符串，因为这是根据前序遍历搞出来的字符串
- 所以构建二叉树，也要根据这个 根->左节点->右节点 的顺序来构建
实现代码：
import java.util.*; //题目啥也没给，节点类也要自己定义一下 class TreeNode{ char value;//节点有值 TreeNode left;//有左孩子节点 TreeNode right;//有右孩子节点 public TreeNode(char value){//构造函数，用于给节点赋值 this.value = value; } } public class Main{ //主函数，用于输入字符串，主要在creatTree方法里来实现 public static void main(String[]args){ Scanner scn = new Scanner(System.in); String str = scn.nextLine(); TreeNode root = creatTree(str); inOrderTraveled(root); } public static int i = 0;//i用于记录字符串中字符的下标 //因为构建过程是递归的，不能用局部变量，所以要在外部设置成静态的 public static TreeNode creatTree(String str){ if(str==null){//如果字符串为空 return null;//直接返回null } //字符串不为空，就进行构构建二叉树的过程 TreeNode root = null;//先创建一个根节点，指向空，这样做是为了初始化 if(str.charAt(i)!='#'){//依次读取字符串中的字符，不为 # 就进行二叉树构造 root = new TreeNode(str.charAt(i));//将读取的字符给节点实例化 i++;//当前读取的字符被用过之后，字符串下标要往后走一位 root.left = creatTree(str);//递归构建左树 root.right = creatTree(str);//递归构建右树 }else{//读取到的字符是 # ，代表空节点，不用构建 i++;//字符串下标往后走一位 } return root;//最后返回根节点即可 } //对构建好的二叉树进行中序遍历，用递归实现就好了 public static void inOrderTraveled(TreeNode root){ if(root==null) return; inOrderTraveled(root.left); System.out.print(root.value+" "); inOrderTraveled(root.right); } }
🎄2. 二叉树的分层遍历
题目：
思路：
- 层序遍历就是一层一层的遍历节点
这题还有一个要求就是，输出的时候将一层的节点放在一行，下一层的节点放在下一行，这就需要用到一个二维数组来储存每一层的节点
我们先来观察一下 层序遍历的过程中，结点进队列和出队列的过程： 请看图
可是如何知道当前访问到的节点是哪一层的呢？ 截取 BFS 遍历过程中的某个时刻：
可以看到，此时队列中的结点是 3、4、5，分别来自第 1 层和第 2 层。这个时候，第 1 层的结点还没出完，第 2 层的结点就进来了，而且两层的结点在队列中紧挨在一起，我们无法区分队列中的结点来自哪一层。
因此，我们在每一层遍历开始前，先记录队列中的结点数量 n（也就是这一层的结点数量），然后一口气处理完这一层的 n 个结点
实现代码：
🎄3. 给定一个二叉树，找到该树中两个指定节点的最近公共祖先
题目：
思路：
祖先的定义： 若节点 p 在节点 root 的左（右）子树中，或 p = root ，则称 root 是 p 的祖先。
根据以上定义，若 root 是 p,q 的 最近公共祖先 ，则只可能为以下情况之一：
①p 和 q 在 root的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
②p = root ，且 q 在 root 的左或右子树中；
③q = root ，且 p 在 root 的左或右子树中；
考虑通过递归对二叉树进行先序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p,q 在节点 root的异侧时，节点 root 即为最近公共祖先，则向上返回 root 。
实现代码：
🎄4. 二叉树搜索树转换成排序双向链表
题目：
思路：
- 已知将二叉搜索树进行中序遍历可以得到
由小到大的顺序排列，因此本题最直接的想法就是进行中序遍历。 - 根据题目的要求1，不能创建新的结点，所以我们
设置一个pre用于指向前驱节点
实现代码：
🎄5. 根据一棵树的前序遍历与中序遍历构造二叉树
题目：
思路：
- 所以我们只需要根据先序遍历得到根节点，然后在中序遍历中找到根节点的位置，它的左边就是左子树的节点，右边就是右子树的节点。
递归生成左子树和右子树
实现代码：
🎄6. 根据一棵树的中序遍历和后序遍历构造二叉树
题目：
思路：
- 和上题几乎一样，只需要
几处小改动 - 因为是给的是
后续遍历，所以构建的时候，读取后续遍历数组要从后往前读取，并且构建的时候是根->右->左
实现代码：
🎄7. 二叉树创建字符串
题目：
思路：
- 我们可以使用递归的方法得到二叉树的前序遍历。在递归时，根据题目描述，我们需要加上额外的括号，会有以下 4 种情况：
① 如果当前节点有两个孩子，那我们在递归时，需要在两个孩子的结果外都加上一层括号；
②如果当前节点没有孩子，那我们不需要在节点后面加上任何括号； 
- 如果
当前节点只有左孩子，那我们在递归时，只需要在左孩子的结果外加上一层括号，而不需要给右孩子加上任何括号；
④如果当前节点只有右孩子，那我们在递归时，需要先加上一层空的括号 () 表示左孩子为空，再对右孩子进行递归，并在结果外加上
考虑完上面的 4 种情况，我们就可以得到最终的字符串。
实现代码：
