🗽非递归实现遍历二叉树（深入理解二叉树）
- 代码每行都有注释，可以一步一步的画着图走一走，多走几遍，理解会上一个档次！
- 前序遍历和中序遍历都用到栈，代码可以说一模一样，只不过打印节点的时机不一样
⭐非递归前序遍历
// 非递归实现前序遍历 public void FDG_reOrderTraversal(TreeNode root){ if (root == null) {//先判断根节点是否空 return;//第一个根节点如果空的话，就直接返回了 } TreeNode cur = root;//设置临时节点cur，通过这个节点来遍历整棵树 Stack<TreeNode> stack = new Stack<TreeNode>();//创建一个栈 while(cur != null || !stack.isEmpty()) {//外循环，先写内循环采写外循环,只要栈不为空，说明还没遍历完成 while (cur != null) {//内循环 stack.push(cur);//将当前cur节点入栈 System.out.print(cur.value+" ");//打印cur节点，前序遍历是在入栈后打印 cur = cur.left;//cur走到原节点的左孩子节点 } //当左子树走完，cur.left肯定会走到空节点，这时候就要走右子树了 TreeNode top = stack.pop();//弹出栈顶节点，注意是弹出，不然会影响后遍历上一个节点的右孩子节点 cur = top.right;//cur走到上一个节点的右孩子节点 } //栈空了，说明遍历完了所有节点 System.out.println(); }
⭐非递归中序遍历
// 非递归实现中序遍历 public void FDG_inOrderTraversal(TreeNode root) { if (root == null) {//先判断根节点是否空 return;//第一个根节点如果空的话，就直接返回了 } TreeNode cur = root;//设置临时节点cur，通过这个节点来遍历整棵树 Stack<TreeNode> stack = new Stack<TreeNode>();//创建一个栈 while(cur != null || !stack.isEmpty()) {//外循环，先写内循环采写外循环,只要栈不为空，说明还没遍历完成 while (cur != null) {//内循环 stack.push(cur);//将当前cur节点入栈，但不打印，需要用它来找左右孩子节点 cur = cur.left;//cur走到原节点的左孩子节点 } //当左子树走完，cur.left肯定会走到空节点，这时候就要走右子树了 TreeNode top = stack.pop();//弹出栈顶节点，注意是弹出，不然会影响后遍历上一个节点的右孩子节点 System.out.print(top.value+" ");//打印cur节点，中序遍历是在节点出栈后打印 cur = top.right;//cur走到上一个节点的右孩子节点 } //栈空了，说明遍历完了所有节点 System.out.println(); }
⭐非递归后序遍历
//非递归后续遍历 public void postOrderTraversalNor(TreeNode root) { if(root == null) return;//第一个根节点如果空的话，就直接返回了 TreeNode cur = root;//设置临时节点cur，通过这个节点来遍历整棵树 Stack<TreeNode> stack = new Stack<>();//创建一个栈 TreeNode pre = null;//用来指定 上一个被打印的元素 while (cur != null || !stack.empty()) {//外循环，只要栈不为空，说明还没遍历完成 while (cur != null) {//内循环 stack.push(cur);//将当前cur节点入栈，但不打印，需要用它来找左右孩子节点 cur = cur.left;//cur走到原节点的左孩子节点 } cur = stack.peek();//查看栈顶节点 if (cur.right == null || cur.right == pre) {//如果栈顶节点的右节点为空，或者已经遍历过了 TreeNode popNode = stack.pop();//弹出栈顶节点并打印 System.out.print(popNode.value + " "); pre = cur;//用pre将遍历（打印）过的节点记录下来 cur = null;//cur要置空，不然就又来一遍了，置空后可以继续查看下一个栈顶节点而不进入内循环 } else {//若栈顶节点右节点不为空 cur = cur.right;//则遍历这个右节点 } } System.out.println(); }
🗽大厂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. 二叉树的分层遍历
题目：
思路：
- 层序遍历就是一层一层的遍历节点
2.这题还有一个要求就是，输出的时候将一层的节点放在一行，下一层的节点放在下一行，这就需要用到一个二维数组来储存每一层的节点
3.我们先来观察一下 层序遍历的过程中，结点进队列和出队列的过程： 请看图
4.可是如何知道当前访问到的节点是哪一层的呢？ 截取 BFS 遍历过程中的某个时刻：
5.可以看到，此时队列中的结点是 3、4、5，分别来自第 1 层和第 2 层。这个时候，第 1 层的结点还没出完，第 2 层的结点就进来了，而且两层的结点在队列中紧挨在一起，我们无法区分队列中的结点来自哪一层。
因此，我们在每一层遍历开始前，先记录队列中的结点数量 n（也就是这一层的结点数量），然后一口气处理完这一层的 n 个结点。
实现代码：
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { //建立一个二维数组来记录每一层的情况 List<List<Integer>> list = new ArrayList(); Queue<TreeNode> queue = new LinkedList<>();//用队列实现层序遍历 if (root==null){ return list; } queue.offer(root);//根节点先入队 while(!queue.isEmpty()) { int n = queue.size();//记录每一层有多少个节点，循环n次 List<Integer> level = new ArrayList();//每一层用一个数组记录 for(int i = 0 ; i<n ; i++){//弹出当前层里的节点， // 变量 i 无实际意义，只是为了循环 n 次 TreeNode top = queue.poll();//弹出队头节点 level.add(top.val);//将弹出的节点加入它所在的那一层 //弹出的时候不要忘了将弹出节点的孩子节点入队 if (top.left != null) { queue.offer(top.left); } if (top.right != null) { queue.offer(top.right); } } list.add(level);//将每一层添加到二维数组中 } return list;//最后返回二维数组即为所求 } }
