| JS 前序遍历、中序遍历、后序遍历、层序遍历详解，深度优先与广度优先区别，附leetcode例题题解答案 | 您所在的位置：网站首页 › 前序遍历后序遍历能推出二叉树 › JS 前序遍历、中序遍历、后序遍历、层序遍历详解，深度优先与广度优先区别，附leetcode例题题解答案 |
JS 前序遍历、中序遍历、后序遍历、层序遍历详解，深度优先与广度优先区别，附leetcode例题题解答案
壹 ❀ 引
按照一天一题的速度，不知不觉已经刷了快两多月的leetcode了，因为本人较为笨拙，一道简单的题有时候也会研究很久，看着提交了两百多次，其实也才解决了70来道简单题，对于二分法，双指针等也只是有个初步概念，并非熟练。 
若你有注意我以往题解文章，会发现我做过的大多题型均以数组和字符串为主。这是因为我在选择题目的时候始终将自己限制在熟悉的知识体系里，我非常害怕树，害怕递归，害怕动态规划。我深知害怕解决不了问题，自己始终得面对它们，所以今天我决定开始啃树了（学习树形结构不是啃树皮），懦弱的心做出稍微勇敢的决定。不积跬步，无以至千里；不积小流，无以成江海，愿你我共勉，那么本文开始。 贰 ❀ 前序遍历、中序遍历、后序遍历在学习树之前，我想大家或多或少会联想到深度优先与广度优先相关概念。我在学习树的卡片时，结果又注意到前序遍历，中序遍历，后序遍历以及层序遍历等概念，这一下我就懵了。所以在学树之前，我们先 了解这些常见的搜索规则。 贰 ❀ 壹 前序遍历前序遍历可以说最符合大家阅读树结构的查询顺序，它满足根节点=>左子树=>右子树的顺序，我们来看个例子： 
如上图，其中A为根节点，B为左子树，C为右子树，所以遍历顺序为ABC。 我们再看看层级复杂点的二叉树结构，如下： 
还是一样的套用上面的规律，首先是根节点A，之后遍历左子树B，而B又有自己的左子树D和右子树E，所以BDE又可以看成一个独立二叉树，因此遍历完B之后，紧接着就是遍历左子树D与右子树E。 E又有自己的左子树和右子树，因此遍历完E紧接着就是GH，到这里左子树完整遍历结束。于是来到右子树C，由于C没有左子树，所以紧接着遍历F，F遍历完又遍历了自己的左子树I，到这里遍历结束。所以完整的顺序为ABDEGHCFI。 我们永远先遍历根节点，紧接着判断有没有左子树，如果有接着遍历，而左子树也可以有自己的左子树与右子树，所以我们可以用递归来做到遍历。 来看一道题，题目来源144. 二叉树的前序遍历，题目描述如下： 给定一个二叉树，返回它的 前序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3输出: [1,2,3] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？ 让我们尝试实现它： /** * @param {TreeNode} root * @return {number[]} */ var preorderTraversal = function(root) { let res = []; // 遍历函数 function traversal(root) { if (root !== null) { // 访问根节点的值 res.push(root.val); if (root.left) { // 递归遍历左子树 traversal(root.left); }; if (root.right) { // 递归遍历右子树 traversal(root.right); }; }; }; traversal(root); return res; }; 贰 ❀ 贰 中序遍历中序遍历满足左子树=>根节点=>右子树的顺序进行查询，我们还是以简单二叉树为例。 
当跑到到根节点B时，先得看看有没有左子树，正好有，所以先遍历了左子树A之后才是B，最后遍历右子树C，所以完整顺序顺序为ABC。 我们再来用中序遍历分析稍微复杂的二叉树，如下图： 
从F开始，先看有没有左子树，因为有于是成功跑到了B，注意此时并不是直接取到B，由于B也有左子树，所以第一个遍历到的节点其实是A，而A没有其它分支了，所以紧接着遍历A的根节点B，然后跑到B的右子树D。而D也有自己的左子树与右子树，所以D不能被立刻遍历，而是先遍历C，然后才是D，最后是E。到这里F节点的左子树全部遍历完成，此时顺序为ABCDEF。 我们再看F的右子树，由于G没有左子树，所以直接遍历G，然后跑到G的右子树I，但I有左子树，所以先取H，再取I。结合上面，此二叉树的中序遍历顺序为ABCDEFGHI，我是以字母顺序提前排好了遍历顺序，大家陌生就多自己走几遍。 那么如何实现一个中序遍历呢，很简单，将前序遍历代码换个顺序就好了，我们始终先遍历节点的左子树，子又有左子树那就一直往下找，找到底才是当前左子树根节点，最后右子树。 看一道题，题目来自leetcode94. 二叉树的中序遍历，描述如下： 给定一个二叉树，返回它的中序遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3输出: [1,2,3] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？ /** * @param {TreeNode} root * @return {number[]} */ var inorderTraversal = function(root) { let res = []; // 遍历函数 function traversal(root) { if (root !== null) { if (root.left) { // 递归遍历左子树 traversal(root.left); }; // 访问根节点的值 res.push(root.val); if (root.right) { // 递归遍历右子树 traversal(root.right); }; }; }; traversal(root); return res; }; 贰 ❀ 叁 后序遍历后序遍历满足左子树=>右子树=>根节点的顺序进行查询，还是从简单二叉树开始： 
从根节点C出发，先访问左子树A，紧接着右子树B，最后根节点C，所以顺序为ABC。 我们再来看一个较为复杂的二叉树，如下： 
还是从根节点I出发，于是成功找到了左子树E，而E也有自己的左子树，所以第一个遍历到了A，紧接着来到E的右子树D，但D也有自己的左右子树，所以第二个遍历的是B，紧接着是C，最后是根节点D，根节点E。到这里，左子树遍历完成，顺序为ABCDE。 我们再来看I的右子树H，由于H有右子树G，所以H不能被遍历，G也有自己的左子树F，于是遍历到了F，G没右子树，于是F之后就是G，谨记着H，到这里I的右子树遍历完成，最后遍历根节点I。所以完整的顺序为ABCDEFGHI，顺序还是与字母顺序一致，大家跟着思路多多感受。 看到题，题目来自leetcode145. 二叉树的后序遍历，题目描述如下： 给定一个二叉树，返回它的后序遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3输出: [1,2,3] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？ 那么如何实现它呢？还是将上面的实现换个顺序即可。 /** * @param {TreeNode} root * @return {number[]} */ var postorderTraversal = function(root) { let res = []; // 遍历函数 function traversal(root) { if (root !== null) { if (root.left) { // 递归遍历左子树 traversal(root.left); }; if (root.right) { // 递归遍历右子树 traversal(root.right); }; // 访问根节点的值 res.push(root.val); }; }; traversal(root); return res; }; 叁 ❀ 层序遍历层序遍历满足从上到下，从左到右一层一层遍历的顺序，以简单的二叉树为例： 
首先从根节点A开始，这是第一层，遍历完成往下一层推进，于是访问到了B和C，完整顺序为ABC。 我们再来看一个较为复杂的二叉树，由于层序遍历理解上还是较为容易，下图遍历顺序为ABCDEFGHI，确实是从上到下从左往右一层层往下推进的遍历顺序。 
来看一道题，题目来自leetcode102. 二叉树的层序遍历，描述如下： 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 示例： 二叉树：[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回其层次遍历结果： [ [3], [9,20], [15,7] ] 让我们来实现它，我们每遍历一层，都会将本层节点装到一个数组里，每往下推进一层，我们都得创建一个新的子数组，实现如下： /** * @param {TreeNode} root * @return {number[][]} */ var levelOrder = function(root) { let res = []; function traversal(root, depth) { if (root !== null) { if (!res[depth]) { res[depth] = []; }; res[depth].push(root.val) if (root.left) { traversal(root.left, depth + 1); }; if (root.right) { traversal(root.right, depth + 1); }; }; }; traversal(root, 0); return res; };关于层序遍历我们来趁热打铁，再来补一道我昨天做的题，题目来自leetcode104. 二叉树的最大深度，描述如下： 给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例： 给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7返回它的最大深度 3 。 注意，由于我们是要统计最大深度，所以第一层就应该是从1开始，这里直接贴代码： /** * @param {TreeNode} root * @return {number} */ var maxDepth = function(root) { let ans = 0; if(root===null){ return ans; }; function traversal(root,deepth){ // 始终取最大数为最深层级 ans = Math.max(ans,deepth) if(root.left){ traversal(root.left,deepth+1); }; if(root.right){ traversal(root.right,deepth+1); }; }; // 从1开始 traversal(root,1); return ans; }; 肆 ❀ 深度优先、广度优先与前序、中序、后序、层序遍历关系那么我们经常听闻的深度优先DFS与广度优先（宽度优先）BFS又和前面的前序、中序、后序、层序遍历又有何关系呢？我想聪明的同学应该已经联想到了，前序、中序、与后序遍历均为深度优先。而层序遍历也就是所谓的广度优先了。 对比不难发现，深度优先更具钻研精神，只要子树还有子，就一直往下查找，至于顺序对应前中后的查找顺序。而广度是将每一层节点遍历完成为止，才会进入下一层。 
伍 ❀ 总
需要说明的是，上述实现代码其实都不是最优做法，部分实现均借鉴了leetcode题解一套拳法👊刷掉n个遍历树的问题一文。因为对于现在的我来说，最易理解的解答要优于更好的性能，至于性能提升还需要日后积累，那么到这里本文结束。 |
【本文地址】