theme: lilsnake

前言

二叉树经常是面试的高频考察点，涉及到的算法数不胜数，而其中最基础的方式就是二叉树的遍历，我们必须弄懂二叉树的遍历，才能更好的进阶二叉树的难点和面试常考点。今天就让我们来了解其中的几种遍历方式(JS版)

1. 递归遍历（重点）
2. 非统一迭代遍历
3. 统一迭代遍历（重点）

递归遍历二叉树

所谓递归，就是函数里面调用函数，这是遍历二叉树最简单的方式。废话不多说，先上代码。

var preorderTraversal = function(root) {
    const arr=[]
    if(!root) return []
    let qx=root=>{
        if(!root) return
        arr.push(root.val)
        qx(root.left)
        qx(root.right)
    }
    qx(root)
    return arr
};

递归前序遍历

这是一个二叉树的前序遍历，遍历顺序为中左右，我们可以发现，先是声明了一个arr数组，如果头结点就为空则返回空数组，接下来我们定义了一个递归函数， 里面的内容先判断当前结点是否为空，为空就退出当前函数，不为空就将此数推入数组，然后再递归二叉树左边，再递归二叉树右边。最后我们调用这个函数，然后返回结果。具体操作可以看下方。

我们以这棵二叉树为例

1. 首先判断当前头结点是否为空，不为空，因此推入数组，数组为[1]
2. 然后递归左边（又回到第一步），1的左边为3，推入数组,数组为[1,3]
3. 然后又递归左边(第一步),推入数组,数组为[1,3,1]
4. 这个时候1的左边为空,那就看右边也为空,则返回上一级调用函数(3的调用函数),3的左边1这个函数调用完毕,看4,4不为空,推入数组,数组为[1,3,1,4]接下来4的情况也和兄弟结点1是一样的,因此返回上一级,这个时候,3的调用函数也全部执行完毕(1和4),也退回上一级调用函数(头结点1),对于头结点1,推入动作已经做完了,左子树也已经全部执行完成,然后也按照一模一样的方式去遍历右子树,我们不难得出[1,3,1,4,5,2,1]的结果,没错,二叉树里也有题主对大家的爱意,这可不赶快点赞收藏评论哈哈哈哈哈. 然后中序(左中右)和后序也是一样的遍历方式,只是推入数据的位置不同,撂下代码,待聪明的你去发掘,此处不赘述.

递归中序遍历

    var inorderTraversal = function(root) {
    const arr=[]
    if(!root) return []
    let qx=root=>{
        if(!root) return
        qx(root.left)
        arr.push(root.val)
        qx(root.right)
       
    }
    qx(root)
    return arr
};

递归后序遍历

    var postorderTraversal  = function(root) {
    const arr=[]
    if(!root) return []
    let qx=root=>{
        if(!root) return
        qx(root.left)
        qx(root.right)
        arr.push(root.val)
       
    }
    qx(root)
    return arr
};

非统一迭代遍历

此处我们的前序和后序是有点像的,因为前序(中左右),后序(左右中),将前序遍历稍加修改为中右左,再反转就变成了后序遍历的方式,但是很难稍加修改达到中序遍历,毕竟我们前面的递归方式可以举一反三,而这个遍历达不到,因此叫非统一迭代遍历.

非统一迭代前序遍历

var preorderTraversal = function(root, res = []) {
  // 如果根节点为空，则返回结果数组
  if (!root) return res;
  
  // 创建一个栈，用于存储待遍历的节点
  const stack = [root];
  
  // 当前节点指针，初始为 null
  let cur = null;
  
  // 循环直到栈为空
  while (stack.length) {
      // 弹出栈顶元素（当前节点）
      cur = stack.pop();
      
      // 将当前节点的值存入结果数组
      res.push(cur.val);
      
      // 若当前节点存在右子节点，则将右子节点入栈
      if (cur.right) stack.push(cur.right);
      
      // 若当前节点存在左子节点，则将左子节点入栈
      if (cur.left) stack.push(cur.left);
  }
  
  // 返回前序遍历结果数组
  return res;
};

这段代码是用来实现二叉树的前序遍历的。下面是它的运行过程的详细说明：

1. 首先定义了一个名为 preorderTraversal 的函数，它接受一个二叉树的根节点 root 和一个结果数组 res，默认为空数组。

2. 如果输入的根节点 root 为空，则直接返回结果数组 res。

3. 创建一个栈 stack，并将根节点 root 入栈。

4. 定义一个变量 cur 用于表示当前节点，初始值为 null。

5. 进入一个循环，直到栈为空为止：

   • 每次循环，从栈顶弹出一个节点，赋给 cur。
   • 将当前节点的值 cur.val 存入结果数组 res。
   • 如果当前节点存在右子节点，则将右子节点入栈。
   • 如果当前节点存在左子节点，则将左子节点入栈。这里的顺序保证了左子节点先于右子节点被遍历。

6. 循环结束后，返回结果数组 res，其中存储了二叉树的前序遍历结果。

现在让我们使用一个简单的二叉树来演示一下这段代码的运行过程：

Copy Code
    1
   / \
  2   3
 / \
4   5

运行过程如下：

1. 初始时，栈 stack 为空，结果数组 res 为空。
2. 将根节点 1 入栈：stack = [1]，res = []。
3. 弹出栈顶元素，当前节点为 1，将其值存入结果数组：stack = []，res = [1]。
4. 将当前节点的右子节点 3 入栈：stack = [3]，res = [1]。
5. 将当前节点的左子节点 2 入栈：stack = [3, 2]，res = [1]。
6. 弹出栈顶元素，当前节点为 2，将其值存入结果数组：stack = [3]，res = [1, 2]。
7. 将当前节点的右子节点 5 入栈：stack = [3, 5]，res = [1, 2]。
8. 将当前节点的左子节点 4 入栈：stack = [3, 5, 4]，res = [1, 2]。
9. 弹出栈顶元素，当前节点为 4，将其值存入结果数组：stack = [3, 5]，res = [1, 2, 4]。
10. 弹出栈顶元素，当前节点为 5，将其值存入结果数组：stack = [3]，res = [1, 2, 4, 5]。
11. 弹出栈顶元素，当前节点为 3，将其值存入结果数组：stack = []，res = [1, 2, 4, 5, 3]。

最终得到的结果数组为 [1, 2, 4, 5, 3]，这就是该二叉树的前序遍历结果。

后序也是差不多的方式,我们给出后序运行代码

非统一迭代后序遍历

var postorderTraversal = function(root, res = []) {
  // 如果根节点为空，则直接返回结果数组
  if (!root) return res;
  
  // 创建一个栈，并将根节点入栈
  const stack = [root];
  // 定义一个变量用于表示当前节点
  let cur = null;
  // 开始循环，直到栈为空为止
  do {
      // 弹出栈顶元素作为当前节点
      cur = stack.pop();
      // 将当前节点的值存入结果数组
      res.push(cur.val);
      // 如果当前节点存在左子节点，则将左子节点入栈
      cur.left && stack.push(cur.left);
      // 如果当前节点存在右子节点，则将右子节点入栈
      cur.right && stack.push(cur.right);
  } while(stack.length);
  
  // 返回结果数组的逆序，即为后序遍历结果
  return res.reverse();
};

而中序就不能这么轻易搞了,我们上代码

非统一迭代中序遍历

var inorderTraversal = function(root, res = []) {
  // 创建一个栈
  const stack = [];
  // 初始化当前节点为根节点
  let cur = root;
  // 开始循环，直到栈为空且当前节点为空为止
  while(stack.length || cur) {
      if(cur) {
          // 如果当前节点存在，则将其入栈，并向左子节点移动
          stack.push(cur);
          // 左
          cur = cur.left;
      } else {
          // 如果当前节点不存在，则说明已经到达最左边的叶子节点
          // 弹出栈顶元素，将其值存入结果数组
          cur = stack.pop();
          res.push(cur.val); 
          // 右
          // 将当前节点指向其右子节点，继续遍历
          cur = cur.right;
      }
  };
  // 返回中序遍历的结果数组
  return res;
};

这段代码的运行过程可以通过以下步骤来解释：

1. 初始化：首先，我们将根节点赋给变量 cur，创建一个空栈 stack 以辅助遍历，创建一个空数组 res 来存储遍历结果。

2. 进入循环：进入循环后，我们会持续执行以下步骤，直到栈为空且当前节点为空：

   • 如果当前节点存在（即非空），则执行以下操作：

     • 将当前节点入栈。
     • 将当前节点指向其左子节点，以便继续向左子树移动。

   • 如果当前节点不存在（即为空），则说明已经到达最左边的叶子节点，此时执行以下操作：

     • 从栈中弹出栈顶元素，将其值存入结果数组。
     • 将当前节点指向弹出的节点的右子节点，以便继续遍历右子树。

3. 循环结束：当栈为空且当前节点为空时，退出循环。

4. 返回结果：返回存储了中序遍历结果的数组 res。

总的来说，这段代码通过使用栈来模拟递归过程，实现了对二叉树的中序遍历。在遍历过程中，首先沿着左子树一直向下遍历，直到找到最左边的叶子节点，然后依次访问节点，并在访问完左子树后再处理右子树。

万能的非递归方法,统一迭代遍历

看了上面两个方法,我们会想有没有一种非递归的方法,可以像递归方式那样把代码的运行过程统一呢,答案是有的,我们先上代码

统一迭代前序遍历

var preorderTraversal = function(root) {
  // 创建一个空数组，用于存储前序遍历的结果
  const arr = [];
  // 创建一个空栈，用于辅助遍历
  const stack = [];
  // 如果根节点存在，则将其入栈
  if (root) stack.push(root);
  // 当栈不为空时，持续遍历
  while (stack.length) {
      // 弹出栈顶元素
      const node = stack.pop();
      // 如果弹出的节点不存在（即为null），说明需要访问栈中的下一个节点
      if (!node) {
          // 将栈中下一个节点的值存入结果数组
          arr.push(stack.pop().val);
          continue;
      }
      // 如果弹出的节点存在，则按前序遍历的顺序处理节点
      // 首先，将右子节点压入栈中
      if (node.right) stack.push(node.right);
      // 然后，将左子节点压入栈中
      if (node.left) stack.push(node.left);
      // 最后，将当前节点再次压入栈中，并压入一个空节点作为标记
      stack.push(node);
      stack.push(null);
  }
  // 返回前序遍历的结果数组
  return arr;
};

这段代码是用非递归的方式实现二叉树的前序遍历，下面详细解释其执行过程：

1. 初始化：

   • 创建一个空数组 arr，用于存储遍历结果。
   • 创建一个空栈 stack，用于辅助遍历。
   • 如果根节点 root 存在，则将其压入栈中。

2. 进入循环：

   • 进入循环后，不断执行以下操作，直到栈为空：

3. 从栈中弹出节点：

   • 每次循环开始，弹出栈顶的节点 node。

4. 处理弹出的节点：

   • 如果 node 为 null，说明当前栈顶节点已经被访问过了，此时应该访问下一个节点。

     • 弹出栈中的下一个节点，将其值存入结果数组 arr 中。

   • 如果 node 不为 null，说明当前节点尚未被访问过，需要按照前序遍历的顺序处理该节点：

     • 首先，如果当前节点有右子节点，将右子节点压入栈中，保证右子节点在左子节点之前被访问。
     • 然后，如果当前节点有左子节点，将左子节点压入栈中。
     • 最后，将当前节点再次压入栈中，并在其后压入一个 null 标记，以便后续区分左右子树的访问顺序。

5. 重复步骤2-4：

   • 持续循环执行以上步骤，直到栈为空。

6. 返回结果：

   • 返回存储了前序遍历结果的数组 arr。

总体来说，这段代码通过模拟递归的方式，利用栈来实现对二叉树的前序遍历。在遍历过程中，通过控制节点的压栈顺序，确保先访问当前节点，然后按照左子节点和右子节点的顺序继续遍历。 而我们要改为中序后序遍历也很容易,只要按照遍历顺序改变入栈顺序即可,直接上代码

统一迭代中序遍历

var inorderTraversal = function(root) {
  // 创建一个空数组，用于存储中序遍历的结果
  const arr = [];
  // 创建一个空栈，用于辅助遍历
  const stack = [];
  // 如果根节点存在，则将其入栈
  if (root) stack.push(root);
  // 当栈不为空时，持续遍历
  while (stack.length) {
      // 弹出栈顶元素
      const node = stack.pop();
      // 如果弹出的节点不存在（即为null），说明需要访问栈中的下一个节点
      if (!node) {
          // 将栈中下一个节点的值存入结果数组
          arr.push(stack.pop().val);
          continue;
      }
      // 如果弹出的节点存在，则按中序遍历的顺序处理节点
      // 首先，将右子节点压入栈中
      if (node.right) stack.push(node.right);
      // 将当前节点再次压入栈中，并压入一个空节点作为标记
      stack.push(node);
      stack.push(null);
      // 然后，将左子节点压入栈中
      if (node.left) stack.push(node.left);
  }
  // 返回中序遍历的结果数组
  return arr;
};

统一迭代后序遍历

var postorderTraversal = function(root) {
  // 创建一个空数组，用于存储后序遍历的结果
  const arr = [];
  // 创建一个空栈，用于辅助遍历
  const stack = [];
  // 如果根节点存在，则将其入栈
  if (root) stack.push(root);
  // 当栈不为空时，持续遍历
  while (stack.length) {
      // 弹出栈顶元素
      const node = stack.pop();
      // 如果弹出的节点不存在（即为null），说明需要访问栈中的下一个节点
      if (!node) {
          // 将栈中下一个节点的值存入结果数组
          arr.push(stack.pop().val);
          continue;
      }
      // 如果弹出的节点存在，则按后序遍历的顺序处理节点
      // 首先，将当前节点再次压入栈中，并压入一个空节点作为标记
      stack.push(node);
      stack.push(null);
      // 然后，依次将右子节点和左子节点压入栈中
      if (node.right) stack.push(node.right);
      if (node.left) stack.push(node.left);
  }
  // 返回后序遍历的结果数组
  return arr;
};

迭代遍历小结

使用统一的迭代方法来遍历二叉树有几个优点：

1. 简化代码逻辑： 使用统一的迭代方法可以减少代码的复杂度和重复性。无论是前序、中序还是后序遍历，都可以采用相似的迭代模式，这样可以减少代码量，并且使得代码更易于理解和维护。
2. 节省空间： 迭代方法通常使用栈或队列来模拟递归过程，相比于递归方法，迭代方法可以显著地减少函数调用的开销，从而节省内存空间。特别是对于大型二叉树或深度较深的二叉树，迭代方法可以更好地管理内存。
3. 避免调用栈溢出： 递归方法在处理深度较大的二叉树时可能会导致调用栈溢出的问题，而迭代方法通过显式地管理栈或队列，可以避免这种情况的发生，从而提高程序的健壮性。
4. 灵活性： 统一的迭代方法可以灵活地应用于不同的遍历顺序，包括前序、中序和后序遍历。开发者可以根据需要选择不同的遍历顺序，而无需修改迭代方法的基本逻辑，从而提高代码的灵活性和可复用性。

总的来说，采用统一的迭代方法来遍历二叉树可以简化代码、节省空间、提高程序的健壮性，并且具有较高的灵活性，是一种有效的二叉树遍历方式。

写在最后

相信通过今天的学习,我们二叉树的基本遍历方式已经非常熟悉了,我们掌握它,后面向着更难的算法题进击吧!