题目描述
对二叉树的遍历是面试中常出现的题目，二叉树的前中后序遍历可以通过递归实现，也可以通过迭代实现，递归的方式在实际使用时，可能会面临内存溢出的风险，所以掌握迭代法的遍历方式，对我们也是很关键的，让我们来一起学会如何通过迭代法来遍历二叉树吧！
前序遍历
首先，将根节点入栈，然后出栈的时候记录其值，同时判断其是否存在右子树和左子树，其中先判断右子树，再判断左子树，存在的话则将其压入栈中，然后循环遍历栈，直到栈为空。
var preorderTraversal = function (root) { if (!root) return []; // 定义最终返回的结果 let result = []; // 定义栈 const stack = [root]; // 只要栈中有元素则进入循环 while (stack.length) { let node = stack.pop(); result.push(node.val); // 如果右孩子存在的话 node.right && stack.push(node.right); node.left && stack.push(node.left); } return result; }; 复制代码
中序遍历
中序遍历的迭代法核心思想在于先遍历完左子树，然后遍历根节点，然后遍历右子树，先使用while循环，遇到左子节点，就让左子节点入栈，如果出栈元素有右子树，就让当前节点指向这颗右子树。
var inorderTraversal = function(root) { // 如果节点为空的情况 if (!root) return []; // 定义最终返回的结果 const result = []; // 当前处理节点 let cur = root; // 定义辅助栈 let stack = []; // 核心循环 while (stack.length || cur) { // 首先遍历左子树 while (cur) { stack.push(cur); cur = cur.left; } // 出栈，存储 let node = stack.pop(); result.push(node.val); if (node.right) { cur = node.right } } return result; }; 复制代码
后序遍历
后序遍历的迭代法核心思路在于，将当前节点的值优先插入栈首，然后左孩子存在将左孩子入栈，右孩子存在将右孩子入栈。
var postorderTraversal = function(root) { if (!root) return [] // 定义最终返回的结果 let result = []; // 定义辅助栈 let stack = [root]; // 只要栈不为空就循环 while (stack.length) { let node = stack.pop(); result.unshift(node.val); // 记住，此处是先左后右 node.left && stack.push(node.left); node.right && stack.push(node.right); } return result }; 复制代码
总结
二叉树前中后序遍历的迭代法是非常重要的思路，主要是借助辅助栈来帮助我们遍历，无论是在工作中还是在面试中，这些思路都会帮助我们写出更加精致的代码。
