vlambda博客
学习文章列表

🌲🌲🌲 前言：

    在二叉树相关的算法中，对于二叉树的搜索和遍历是绕不开的话题「绕开了当我没说😬」。如果你对二叉树的搜索、遍历还没有掌握的很清楚，那么咱就一起来康康。内容包括『二叉树的前序、中序、后序遍历的递归和迭代，以及深度优先搜索、广度优先搜索』 ，如果这几种都掌握了，也希望能看看有什么不对的地方，本算法菜鸟不胜感激。💐

🌲二叉树遍历

    二叉树的遍历包括但是不限于前序、中序、后序、层序、垂序等遍历方式，都是将二叉树所有的节点都访问一遍，然后按照不同的顺序输出节点的值。这里只说一下对前中后序以及层序遍历的想法，对别的方式有兴趣的可以自行搜索哦！🤡

📋 概念总结

前序遍历：从二叉树的根节点出发，当第一次到达节点时就输出节点数据，按照先向左再向右的方向访问。

中序遍历：从二叉树的根节点出发，当第二次到达节点时就输出节点数据，按照先向左再向右的方向访问。

后序遍历：从二叉树的根节点出发，当第三次到达节点时就输出节点数据，按照先向左再向右的方向访问。

层次遍历：从二叉树的根节点出发，按照树的层次自上而下的遍历二叉树。

    Tipes： 不管哪种遍历方式，都是从二叉树的「根节点」开始的，不同的遍历方式是在不同的时间点输出节点的内容。

我自爆第一次学习遍历的时候这概念看好多遍硬是看不懂😂。

    首先不管哪种遍历方式，每个节点都会被访问到。如果把遍历位置比做指针的话，那么指针在每个节点都有三次不同时机的驻留：

1. 在遍历他的左子树之前；

2. 在递归完他的左子树之后，递归他的右子树之前；

3. 在递归他的右子树之后；

    那么我们对比上面的概念，正好每一次驻留都对应我们所说的前序、中序、后序遍历。

前序遍历 --> 根在前，从左往右，一棵树的根永远在左子树前面，左子树在右子树前面「根、左、右」；

中序遍历 --> 根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面 「左、根、右」；

后序遍历 --> 根在后，从左往后，一个数的左子树永远在右子树前面，右子树在根前面 「左、右、根」；

🔖 递归模版

    上面的概念看得干巴巴的，下面来写点代码润润，先从最简单的递归开始。🐋

🔵 前序遍历递归模版

     前序遍历就是根节点在左子树前面，左子树在右子树前面，所以我们在遍历的时候要先把根节点保存，然后再保存左子树，最后保存右子树。

验证一下输出结果：「借用一下力扣的编辑器，哈啊哈😄」

总结一下模版：

//「根、左、右」arr = []recursive (root) { if(!root) return; arr.push(root.val); // 根节点在最前面 recursive(root.left); // 然后是左子树 recursive(root.right); // 最后是右子树}

🔴 中序遍历递归模版

    中序遍历就是左子树在根节点前面，根节点在右子树前面，所以先遍历所有的左子树再根节点，最后是右子树。

验证一下输出结果：

总结一下模版：

arr = []recursive (root) { if(!root) return; recursive(root.left); // 先遍历所有的左子树 arr.push(root.val); // 到尽头没有左子树，当前节点为根节点 recursive(root.right); // 最后遍历所有右子树「还是先找左节点」}

🟡 后序遍历递归模版

    后序遍历就是左子树在左子树前面，右子树在根节点前面，所以先遍历所有的左子树再遍历右子树，最后是根节点。

验证一下输出结果：

总结一下模版：

arr = []recursive (root) { if(!root) return; recursive(root.left); // 先遍历所有的左子树 recursive(root.right); // 然后遍历所有右子树「还是先找左节点」 arr.push(root.val); // 到尽头没有左子树和右子树，当前节点为根节点}

🔘 总结一下

    分析了一波，但是在代码层面来看，也只不过是调整了保存节点值的顺序，但是分析的过程对于接下来的迭代思想还是很有帮助的，所以建议多看看哦！「骗浏览哈哈」

    再有就是，三种遍历方式都是沿着一条树枝访问到树的最深处，然后再换一个方向到最深处，这个就是深度优先搜索DFS。看来前序、中序、后序遍历都是基于DFS的，至于DFS后面再说。

💽 迭代思想

    看了上面的，心里是不是想：递归简直so easy，把模版记下来不久ok了，其实吧二叉树的遍历都是最基础的题目，主要还是在复杂难度的二叉树题目中还要更多别的操作。下面我们用迭代思想去实现二叉树的前序、中序、后序遍历。用迭代思想去做也是很简单的，就是替换一下递归函数。不过迭代思想涉及到栈数据结构，所以还是再看看哈。😊

> 迭代：不断用旧值递推新值

> 栈：先进后出

⚾️ 前序遍历迭代法

    首先先明确一下前序遍历输出节点的顺序：「根、左、右」,那么栈则是先进后出，那么怎么保证输出顺序那？那肯定就是按照倒序入栈「右、左、根」，那么我们出栈顺序就是「根、左、右」，那我们怎么保证让根最后一个入栈最先出栈而且最初的根节点一定是最前面的？毕竟按照我们上面递归的时候的解释，每个节点都有可能成为局部树根节点。

    那么我们就每次先把根节点入栈，然后立即出栈，再将根节点的右节点，左节点入栈，然后再执行出栈的操作，这时候栈顶的元素就是将作为根节点的省上一级根节点的左节点，这样就保证了我们根节点最先出栈。

    光看太干巴，来点代码润润：

function(root) {  let arr = [];  if (!root) return arr;  let zhan = [];  let newNode = '';  zhan.push(root); // 根节点先入栈 while (zhan.length) {  newNode = zhan.pop(); // 栈顶元素就出栈  arr.push(newNode.val); // 保存出栈元素内容 if (newNode.right) { // 右节点入栈 zhan.push(newNode.right)  }  if (newNode.left) { // 左节点入栈 zhan.push(newNode.left)  }  }  return arr; };

前序遍历思想：

    根节点在迭代之前进栈，迭代开始立即执行出栈操作，出栈元素右子树进栈，再左子树进栈，然后出栈，再次执行上面的流程。「虽然右子树先进，但是因为是栈结构，先进后出，所有左子树肯定再右子树前面」。

Tipes：根节点在迭代之前进栈，然后就出栈「根，左，右」。

🥎 中序遍历迭代法

    首先先明确一下中序遍历输出节点的顺序：「左、根、右」，那么我们是不是还要按照前序遍历那样倒序入栈？显然不是，前序遍历是根节点在最前面，所以我们从二叉树的最顶部开始，一层一层往下就行。那么中序遍历，是左节点在最前面，我们肯定要遍历到左子树的最深处，才能找到最前面的那一个节点。然后再按照左节点->根节点->右节点的顺序去输出内容，「⚠️我们一直说的每个节点都可能成为局部二叉树的根节点」，上代码：

function(root) {  let arr = [];  let zhan = [];  while(root || zhan.length){  while (root) { // 将所有左子树入栈 zhan.push(root);  root = root.left;  };  root = zhan.pop(); // 到二叉树最低，左子树为空，栈顶元素做为根节点出栈 arr.push(root.val); // 已经出栈元素就是局部二叉树的根节点，按照顺序再去找有节点 root = root.right; // 右节点入栈，先进后出=>后进先出 如果序后没有节点，则保证了顺序 };  return arr;};

中序遍历思想：

    先将所有左子树进栈「包括根节点」，到最低左子树为空的时候出栈，这时候出栈元素作为根节点，因为左节点为空，所以直接保存根节点即弹出元素内容，然后按顺序该右子树了，判断是否存在右子树，存在则压入右子树，然后以压入的右节点作为局部二叉树的根节点，继续判断是否存在左子树，存在继续将所有左子树入栈。

Tipes：优先左子树进栈，这一树枝上的左子树都进栈之后执行出栈操作，出栈的时候先保存弹出元素，然后判断弹出元素的右子树上是否有左子树；「左，根，右」。

🎾 后序遍历迭代法

    首先先明确一下后序遍历输出节点的顺序：「左、右、根」，后序遍历根节点在最后面，那么其实和前序遍历差不多，修改一下顺序就行。

    我们让添加元素的时候，从数组头部添加，那么就确保根节点肯定在最后面，然后先压入左节点，再压入右节点，这样就保证右节点先出栈，但因为是从头部添加数组，则左节点的内容肯定在右节点前面。

function(root) { let arr = [];  if (!root) return arr;  let zhan = [];  let newNode = '';  zhan.push(root); // 根节点先入栈 while (zhan.length) {  newNode = zhan.pop(); // 栈顶元素就出栈  arr.unshift(newNode.val); // 保存出栈元素内容 if (newNode.left) { // 左节点入栈 zhan.push(newNode.left)  }  if (newNode.right) { // 右节点入栈 zhan.push(newNode.right)  }  }  return arr;};

还有一种写法：

function(root) {  let arr = [];  let zhan = [];  while (root || zhan.length) {  while (root) {  arr.push(root.val);  zhan.push(root);  root = root.right;  };  root = zhan.pop();  root = root.left;  };  return arr.reverse(); };

    先将所有右子树进栈，进栈的同时保存元素内容，然后将出栈的元素的左子树入栈，如果左子树有右子树元素，则继续将右子树进栈，同时保存元素内容；「进栈的同时保存进栈元素」最后倒序输出元素数组。

Tipes：将所有右子树先进栈，进栈的同时保存元素内容，最后形成「根，右，左」，再倒序输出。

    后序遍历思想太多，不总结了大佬们自己体会「留个作业哈哈」。

🧩 二叉树搜索

    看到这的大佬，大概有个问题为什么二叉树的遍历我把层序遍历漏掉了😂。其实不是，因为二叉树的层序遍历每次出现的时候都伴随着深度优先搜索、广度优先搜索。所以我想把层序遍历放到二叉树搜索里面。

📋 概念总结

深度优先遍历（DFS）：沿着树的深度遍历，当所有边都被探寻返回到开始的节点，属于盲目搜索，无法保证搜索的路径为最短路径，可以查看有哪些路径可以选择。

广度优先遍历（BFS）：从根结点开始，沿着宽度遍历节点，属于盲目搜索。

 🧠 思想理解

我们从二叉树的层序遍历来说，更加具体一些：

🌜DFS

function (root) { const res = []; function traversal(root, index) { if (root !== null) { if (!res[index]) res[index] = [];// 如果index层对应的下标没有则新增一层 res[index].push(root.val);// 加入到对应层的数组元素中 traversal(root.left, index + 1); // 继续向下 traversal(root.right, index + 1); } } traversal(root, 0); // 用层高定位二维数组每一层的位置 return res;}

🌛BFS

// 使用了队列「先进先出」function(root) {  const all = [];  if (!root) return all;  const one = [];  one.push(root);  while(one.length !== 0) {  let lengthA = one.length; // 保存一层节点的个数 all.push([]); // 保存本层的节点内容 for (let i = 0; i < lengthA; i++) { // 遍历本层的每一个节点 let getOne = one.shift(); // 从头部取 all[all.length - 1].push(getOne.val);  // 将下一层的按顺序从数组尾部加入 if (getOne.left) {  one.push(getOne.left);  };  if (getOne.right) {  one.push(getOne.right);  };  };  };  return all;  };

💐💐💐 结语：

    终于写完了，作为一个算法菜鸡，这点东西写的我满头大汗😢。不过也算是小小的总结了一下，巩固了一下。下次再遇到不会直接就放弃，最起码还能挣扎一下哈哈。

    毕竟是算法菜鸡，如果文章内容有误，希望各位大佬指出，关于DFS和BFS的多种写法，希望大佬们教教我，不胜感激。

    最后祝各位大佬学习进步，事业有成！🎆🎆🎆