2023年6月22日发(作者：)

Java实现⼆叉树的先序、中序、后序、层序遍历（递归+⾮递归⽅法），附带⾃⼰深⼊浅出的讲解 ⼆叉树（Binary tree）是树形结构的⼀个重要类型，也⼀种⾮常重要的数据结构，更是算法题中⾼频出现的知识点，不管是为了应付⼯作还是⾯试，都有必要深度学习⼀下。⼆叉树有多种遍历⽅法，如：层次遍历、深度优先遍历、⼴度优先遍历等。本⽂只涉及了⼆叉树的先序、中序、后序和层序的递归和⾮递归遍历。莫贪多，学好这四种就完全够⽤了。概念看到⽹上诸多相关⽂章都很⾼⼤上，内容确实很丰富，但是总觉得对初学者不太友好。我在初学⼆叉树的时候，就总是看不懂其中的门道，感觉⾃⼰是理解了，过⼏天算法题还是不会解决。后来花费了很⼤的精⼒才总结出⼀些规律，不⼀定适合所有⼈，但是想分享出来供⼤家参考。所以，在学习代码之前，有必要先来了解⼀下先序、中序、后序和层序的概念。1. 先序、中序、后序遍历关系：先序遍历（根左右）：考察到⼀个节点后，⽴刻输出该节点的值，然后继续遍历其左右⼦树；根在前，从左往右，⼀棵树的根永远在左⼦树前⾯，左⼦树⼜永远在右⼦树前⾯；核⼼：先输出⾃⼰，再遍历⼦树。中序遍历（左根右）：考察到⼀个节点后，将其暂存，遍历完左⼦树后，再输出该节点的值，然后遍历右⼦树；根在中，从左往右，⼀棵树的左⼦树永远在根前⾯，根永远在右⼦树前⾯；核⼼：⾃⼰的左⼦没有数据，才将⾃⼰输出。后序遍历（左右根）：考察到⼀个节点后，将其暂存，遍历完左右⼦树后，再输出该节点的值；根在后，从左往右，⼀棵树的左⼦树永远在右⼦树前⾯，右⼦树永远在根前⾯；核⼼：⾃⼰的左⼦和右⼦都没有数据，才将⾃⼰输出。上图中的⼆叉树，分别⽤三种遍历⽅法得到的结果：先序：1-2-4-6-7-8-3-5中序：4-7-6-8-2-1-3-5后序：7-8-6-4-2-5-3-1观察：综合上述结果，对照概念，结合图例中的⽩线，仔细研究⼀下：不管哪种遍历⽅法，考察节点的顺序都是沿着⽩线⽅向⾛的，输出的结果也都是沿着⽩线顺序输出的。其中，考察节点的顺序就是⼆叉树的遍历⽅向。结论：⽆论是哪种遍历⽅法，考察节点的顺序都是⼀样的（留意图中的⽩线⽅向）；只不过考察了节点后，有时候是直接输出（先序），有时候是将其暂存（中序、后序），需要在之后的过程中输出。2. 层序层序⽐较好理解，参照上图中的 绿⾊剪头（→）⽅向。就是按照树的深度，从上到下，从左到右，依次输出：层序：1-2-3-4-5-6-7-8递归和⾮递归实现如果概念理解了，那代码就跟容易理解了。每种遍历⽅法列举2种实现⽅式：递归⽅式、⾮递归⽅式；递归⽅法：很好理解，就是按照⽩线⽅向遍历⼆叉树就⾏了，区别就是在不同的位置输出节点数据。⾮递归⽅法：因为遍历过程涉及到了节点的回溯（即：遍历完节点的左⼦树后，再返回节点，接着遍历节点的右⼦树），为了能准确的找回该节点，采⽤了栈结构-Stack（先进后出）对节点进⾏暂存。树节点的创建：public class TreeNode { int val;

TreeNode left; TreeNode right; // 构造⽅法 public TreeNode(int val) { = val; }}1.先序遍历递归实现 /** —————————— 先序遍历：递归实现 —————————— */ public static void recursionPreorderTraversal(TreeNode root) { if (root != null) { ("输出节点：" + root .val); recursionPreorderTraversal(); recursionPreorderTraversal(); } }⾮递归实现 为了⽅便理解，我把遍历过程的描述全部写在了代码注释⾥： /** —————————— 先序遍历：⾮递归 —————————— */ public static void preorderTraversal(TreeNode root) { if(root == null) return; // ⽤来暂存节点的栈 Stack treeNodeStack = new Stack(); // 新建⼀个游标节点为根节点 TreeNode node = root; // 当遍历到最后⼀个节点的时候，⽆论它的左右⼦树都为空，并且栈也为空 // 所以，只要不同时满⾜这两点，都需要进⼊循环 while (node != null || !y()) { // 若当前考查节点⾮空，则输出该节点的值 // 由考查顺序得知，需要⼀直往左⾛ while (node != null) { ("输出节点：" + ); // 为了之后能找到该节点的右⼦树，暂存该节点 (node); node = ; } // ⼀直到左⼦树为空，则开始考虑右⼦树 // 如果栈已空，就不需要再考虑，弹出栈顶元素，将游标等于该节点的右⼦树 if (!y()) { node = (); node = ; } } }2.中序遍历递归实现 /** —————————— 中序遍历：递归 —————————— */ public static void recursionMiddleorderTraversal(TreeNode root) { if (root != null) { recursionMiddleorderTraversal(); ("输出节点：" + ); recursionMiddleorderTraversal(); } }⾮递归实现中序和先序的⾮递归遍历⾮常类似，唯⼀区别是考查到当前节点时，并不直接输出该节点。⽽是当考查节点为空时，从栈中弹出的时候再进⾏输出(永远先考虑左⼦树，直到左⼦树为空才访问根节点)。如果过程不理解，可以参照“前序遍历”的注释描述。 /** —————————— 中序遍历：⾮递归 —————————— */ public static void middleorderTraversal(TreeNode root) { if(root == null){ return; } Stack treeNodeStack = new Stack(); TreeNode node = root; while (node != null || !y()) { while (node != null) { (node); node = ; } if (!y()) { node = (); ("输出节点：" + ); node = ; } } }3.后序遍历递归实现 /** —————————— 后序遍历：递归 —————————— */ public static void recursionPostorderTraversal(TreeNode root) { if (root != null) { recursionPostorderTraversal(); recursionPostorderTraversal(); ("输出节点：" + ); } }⾮递归实现虽然也是使⽤栈结构做节点暂存，但是后序遍历和先序、中序遍历不太⼀样，要特别唠叨⼏句。因为后序遍历在决定是否可以输出当前节点的值的时候，需要考虑其左右⼦树是否都已经遍历完成。显然⼀个游标已经不够⽤了，所以需要再设置⼀个游标 - lastNode，⽤来保存当前输出的节点，⽤来做为下次对⽐的依据。 过程简单分析：若 node 的右节点 为 null，说明已经是最底层节点，直接输出。如：输出节点【8】的场景， == null；节点输出以后，把 lastNode 节点设置成当前节点，将当前游标节点node设置为空，下⼀轮就可以访问栈顶元素。如：输出节点【8】以后，lastNode 设置成8，node == null，程序进⼊下⼀次while循环，直接⾛到“node = ();”上，查看栈顶元素，此时 node 被赋值 【6】；若 lastNode 等于当前考查节点的右⼦树，表⽰该节点的左右⼦树都已经遍历完成，则可以输出当前节点。如：输出节点【6】的场景， == lastNode == 8 。 /** —————————— 后序遍历：⾮递归 —————————— */ public static void postorderTraversal(TreeNode root) { if(root == null){ return; } Stack treeNodeStack = new Stack(); TreeNode node = root; TreeNode lastNode = root; while (node != null || !y()) { while (node != null) { (node); node = ; } // 查看当前栈顶元素 node = (); // 如果其右⼦树也为空，或者右⼦树已经访问过，则可以直接输出当前节点的值 if ( == null || == lastNode) { ("输出节点：" + ); (); // 把输出的节点赋值给lastNode游标，作为下次⽐对的依据 lastNode = node; node = null; } // 否则，继续遍历右⼦树 else { node = ; } } }4.层序遍历层序遍历⼆叉树，使⽤了队列结构-Queue（先进先出）来实现。先将根节点⼊队列，只要队列不为空，然后出队列并访问，接着将访问节点的左右⼦树依次⼊队列。如此操作，可以保证上层的节点⼀定会在下层之前输出。 /** —————————— 层序遍历 —————————— */ public static void levelTraversal(TreeNode root){ if(root == null) return; Queue queue = new LinkedList(); (root); while(!y()){ TreeNode temp = (); n("输出节点：" + ); if( != null) (); if( != null) (); } }补充：层序遍历⼆叉树，并且分层打印？原理和上⾯是⼀样的，为了记录每层该打印⼏条数据，我们需要再定义2个变量：star，end。 public static ArrayList> printTree(TreeNode pRoot) { ArrayList> res = new ArrayList<>(); if (pRoot == null) { return res; } // start 记录从队列中取出的节点数量，end记录每⾏的节点数 int start = 0; // 还没开始从queue取数据，所以初始值是0 int end = 1; // 根节点只有1个，初始值是1 Queue queue = new LinkedList<>(); (pRoot); List tempList = new ArrayList<>(); while(!y()){ TreeNode temp = (); (); start ++; if ( != null) { (); } if ( != null) { (); } // 当从队列中取出的数量等于存⼊的⽗节点数量时，说明当前层已经遍历完，换⾏ if (end == start) { (new ArrayList<>(tempList)); end = (); start = 0; (); } } return res; }总结1. ⼆叉树的先序、中序、后序、层序遍历是⾯试算法题中的⾼频考点；2. 因为递归写法⾮常简单，建议⼀定要掌握⾮递归的⽅法，3. ⾮递归的⽅式⾮常利于解决场景问题，不管是⾯试出的场景，还是实际⽣产场景；4. 先序、中序、后序遍历使⽤栈结构（Stack）来解决节点暂存的问题；5. 先序、中序遍历过程类似，区别在节点的输出时机，⽽后序遍历因为需要考虑节点回溯后对⽐，所以引⼊了⼀个游标lastNode，⽤来保存上⼀次输出的Node；6. 层序遍历使⽤队列结构（Queue）来保障上下层节点的输出顺序；