如何从JS执行栈视角，图解递归算法在二叉树前中后遍历中的应用？

本文共计4685个文字，预计阅读时间需要19分钟。

栈+二叉树是递归算法的同义词，在初上手时会，一旦经历过题目，就再也不用手忙脚乱。由于LeetCode不方便调试，题目做错了也不知道错在哪，最后无奈‘

壹 ❀ 引

想必凡是接触过二叉树算法的同学，在刚上手那会，一定都经历过题目无从下手，甚至连题解都看不懂的痛苦。由于leetcode不方便调试，题目做错了也不知道错在哪里，最后无奈的cv答案后心里还不断安慰自己。不甘心想着要不直接背模板吧，可当天一知半解的记住了，不到半个月回头面对一道曾做过的简单二叉树题，脑袋里跟看一道新题一样。

那么二叉树对于我这个不是计算机专业的人来说难在哪呢？第一，我始终无法在脑中构建递归的过程，就像我的思维空间不足以支撑递归在我的脑中运行，大致脑补了两步就直接乱套了，我想象不出这个过程。

第二，对于二叉树的前中后层序遍历始终是一知半解，因为不理解递归到底怎么运行的，所以心里其实不知道它们三者到底差异在哪，为啥arr.push(root.val)写的地方不同，就实现了三种不同遍历方式？小小的脑袋里留下了大大的疑惑。

const traverse = (root) => { if (root === null) { return; }; // 前序遍历 traverse(root.left); // 中序遍历 traverse(root.right); // 后序遍历 }

那么本文就是为了解答这些疑问而来，我将从递归说起，用图解JS调用栈的方式阐述递归思路，帮助大家在脑中构建这个过程，之后再解释二叉树前中后序遍历为什么逻辑处理的位置不同，就能达到不同差异，那么本文开始。