二叉树在面试实战中，花样非常多。本节只是个开头，在后面几个专题、包括最后的大厂真题实战环节中，我们都不会停止对二叉树相关考点的学习和探讨。

在本节，有以下三个命题方向需要大家重点掌握：

迭代法实现二叉树的先、中、后序遍历
二叉树层序遍历的衍生问题
翻转二叉树

这三个方向对应的考题都比较经典。与此同时，解决这些问题涉及到的思路和编码细节，也会成为各位日后解决更加复杂的问题的基石。因此，虽然本节篇幅略长，但还是希望各位能够倾注耐心，给自己充分的时间去理解和消化这些知识。

# “遍历三兄弟”的迭代实现

经过第5节的学习，相信各位已经将二叉树先、中、后序遍历的递归实现吃得透透的了。在使用递归实现遍历的过程中，我们明显察觉到，“遍历三兄弟”的编码实现也宛如孪生兄弟一样，彼此之间只有代码顺序上的不同，整体内容基本是一致的。这正是递归思想的一个重要的优点——简单。

这里的“简单”并不是说学起来简单。相反，结合笔者早期的读者调研来看，大部分同学都认为递归学起来让人很难受（这也是正常的）。初学递归的人排斥递归，大部分是出于对“函数调用自身”这种骚操作的不适应。但只要你能克服这种不适应，并且通过反复的演练去吸收这种解题方法，你就会发现递归真的是个好东西。因为通过使用递归，我们可以把原本复杂的东西，拆解成非常简单的、符合人类惯用脑回路的逻辑。

这样说可能还是有点抽象，不过没关系，接下来我会讲解“遍历三兄弟”对应的迭代解法。等我们学完这坨东西之后，心怀疑惑的同学不妨拿迭代法的代码和第5节中递归法的代码比较一下，相信你会毫不犹豫地回头对递归说上一句“真香！”。

从先序遍历说起

题目描述：给定一个二叉树，返回它的前序（先序）遍历序列。

示例:

输入: [1,null,2,3]

1   
 \   
  2   
 /  
3 
输出: [1,2,3]

@前端进阶之旅: 代码已经复制到剪贴板

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路分析

注意最后那一行小字：“递归算法很简单，你可以通过迭代算法完成吗？”，对递归算法有疑问的同学，趁这个机会赶紧复习下第五小节，本节我们只讲迭代法。
前面两个小节，我们一直在强调，递归和栈有着脱不开的干系。当一道本可以用递归做出来的题，突然不许你用递归了，此时我们本能的反应，就应该是往栈上想。

在基于栈来解决掉这个题之前，我要先跟平时用 leetcode 刷题的各位强调一个常识。

现在大家回头看这道题目给我们的输入和输出：输入看似是一个数组，实则不是。大家谨记，二叉树题目的输入只要没有额外强调，那么一般来说它都是基于这样的一个对象结构嵌套而来的：

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

@前端进阶之旅: 代码已经复制到剪贴板

比如这样：

const root = {
  val: "A",
  left: {
    val: "B",
    left: {
      val: "D"
    },
    right: {
      val: "E"
    }
  },
  right: {
    val: "C",
    right: {
      val: "F"
    }
  }
};

@前端进阶之旅: 代码已经复制到剪贴板

话说回来，为啥题上给的不是对象，而是这样的一个数组呢：

[1,null,2,3]

@前端进阶之旅: 代码已经复制到剪贴板

这其实是一种简化的写法，性质跟咱们写伪代码差不多。它的作用主要是描述二叉树的值，至于二叉树的结构，我们以题中给出的树形结构为准：

@前端进阶之旅: 代码已经复制到剪贴板

OK，了解了输入内容，现在再来看输出：

[1,2,3]

@前端进阶之旅: 代码已经复制到剪贴板

这里这个输出就简单多了，它是一个真数组。为什么可以判断它是一个真数组呢？因为题目中要求你输出的是一个遍历序列，而不是一个二叉树。因此大家最后需要塞入结果数组的不是结点对象，而是结点的值。

注意：

以上的出参入参规律，是针对 leetcode 及其周边 OJ 来说的。OJ 中这样编写题目描述，是情理之中，因为 OJ 本身是支持多语言的，它只能对最通用的一部分信息进行透出。在面试场景下，不排除一些公司可能会贴心地把 JS 版本的出参和入参给出来，但更多的还是会直接复制粘贴 leetcode 或者其它一些算法书中的原题。如果你对题目的出参和入参有疑问，请大胆地对面试官说出你的困惑——没有一个正常面试官会在题目描述上为难你，他比你更急切地想看到你刷刷写代码的英姿。
回到题目上来。我们接着栈往下说，题目中的出参是一个数组，大家仔细看这个数组，它像不像是一个栈的出栈序列？实际上，做这道题的一个根本思路，就是通过合理地安排入栈和出栈的时机、使栈的出栈序列符合二叉树的前序遍历规则。

前序遍历的规则是，先遍历根结点、然后遍历左孩子、最后遍历右孩子——这正是我们所期望的出栈序列。按道理，入栈序列和出栈序列相反，我们似乎应该按照右->左->根这样的顺序将结点入栈。不过需要注意的是，我们遍历的起点就是根结点，难道我们要假装没看到这个根结点、一鼓作气找到最右侧结点之后才开始进行入栈操作吗？答案当然是否定的，我们的出入栈顺序应该是这样的：

将根结点入栈
取出栈顶结点，将结点值 push 进结果数组
若栈顶结点有右孩子，则将右孩子入栈
若栈顶结点有左孩子，则将左孩子入栈

这整个过程，本质上是将当前子树的根结点入栈、出栈，随后再将其对应左右子树入栈、出栈的过程。

重复 2、3、4 步骤，直至栈空，我们就能得到一个先序遍历序列。

编码实现

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const preorderTraversal = function(root) {
  // 定义结果数组
  const res = []  
  // 处理边界条件
  if(!root) {
      return res
  }
  // 初始化栈结构
  const stack = [] 
  // 首先将根结点入栈
  stack.push(root)  
  // 若栈不为空，则重复出栈、入栈操作
  while(stack.length) {
      // 将栈顶结点记为当前结点
      const cur = stack.pop() 
      // 当前结点就是当前子树的根结点，把这个结点放在结果数组的尾部
      res.push(cur.val)
      // 若当前子树根结点有右孩子，则将右孩子入栈
      if(cur.right) {
          stack.push(cur.right)
      }
      // 若当前子树根结点有左孩子，则将左孩子入栈
      if(cur.left) {
          stack.push(cur.left)
      }
  }
  // 返回结果数组
  return res
};

@前端进阶之旅: 代码已经复制到剪贴板

# 异曲同工的后序遍历迭代实现

思路分析

后序遍历的出栈序列，按照规则应该是 左 -> 右 -> 根 。这个顺序相对于先序遍历，最明显的变化就是根结点的位置从第一个变成了倒数第一个。
如何做到这一点呢？与其从 stack 这个栈结构上入手，不如从 res 结果数组上入手：我们可以直接把 pop 出来的当前结点 unshift 进 res 的头部，改造后的代码会变成这样：

while(stack.length) {
  // 将栈顶结点记为当前结点
  const cur = stack.pop() 
  // 当前结点就是当前子树的根结点，把这个结点放在结果数组的头部
  res.unshift(cur.val)
  // 若当前子树根结点有右孩子，则将右孩子入栈
  if(cur.right) {
    stack.push(cur.right)
  }
  // 若当前子树根结点有左孩子，则将左孩子入栈
  if(cur.left) {
    stack.push(cur.left)
  }
}

@前端进阶之旅: 代码已经复制到剪贴板

大家可以尝试在大脑里预判一下这个代码的执行顺序：由于我们填充 res 结果数组的顺序是从后往前填充（每次增加一个头部元素），因此先出栈的结点反而会位于 res 数组相对靠后的位置。出栈的顺序是当前结点 -> 当前结点的左孩子 -> 当前结点的右孩子，其对应的 res 序列顺序就是右 -> 左 -> 根。这样一来，根结点就成功地被我们转移到了遍历序列的最末尾。

现在唯一让人看不顺眼的只剩下这个右孩子和左孩子的顺序了，这两个孩子结点进入结果数组的顺序与其被 pop 出栈的顺序是一致的，而出栈顺序又完全由入栈顺序决定，因此只需要相应地调整两个结点的入栈顺序就好了：

// 若当前子树根结点有左孩子，则将左孩子入栈
if(cur.left) {
  stack.push(cur.left)
}  
// 若当前子树根结点有右孩子，则将右孩子入栈
if(cur.right) {
  stack.push(cur.right)
}

@前端进阶之旅: 代码已经复制到剪贴板

如此一来，右孩子就会相对于左孩子优先出栈，进而被放在 res 结果数组相对靠后的位置，左 -> 右 ->根的排序规则就稳稳地实现出来了。

我们把以上两个改造点结合一下，就有了以下代码：

编码实现

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const postorderTraversal = function(root) {
  // 定义结果数组
  const res = []  
  // 处理边界条件
  if(!root) {
      return res
  }
  // 初始化栈结构
  const stack = [] 
  // 首先将根结点入栈
  stack.push(root)  
  // 若栈不为空，则重复出栈、入栈操作
  while(stack.length) {
      // 将栈顶结点记为当前结点
      const cur = stack.pop() 
      // 当前结点就是当前子树的根结点，把这个结点放在结果数组的头部
      res.unshift(cur.val)
      // 若当前子树根结点有左孩子，则将左孩子入栈
      if(cur.left) {
        stack.push(cur.left)
      }  
      // 若当前子树根结点有右孩子，则将右孩子入栈
      if(cur.right) {
        stack.push(cur.right)
      }
  }
  // 返回结果数组
  return res
};

@前端进阶之旅: 代码已经复制到剪贴板

思路清奇的中序遍历迭代实现

思路分析

经过上面的讲解，大家会发现先序遍历和后序遍历的编码实现其实是非常相似的，它们遵循的都是同一套基本框架。那么我们能否通过对这个基本框架进行微调、从而同样轻松地实现中序遍历呢？

答案是不能，为啥不能？因为先序遍历和后序遍历之所以可以用同一套代码框架来实现，本质上是因为两者的出栈、入栈逻辑差别不大——都是先处理根结点，然后处理孩子结点。而中序遍历中，根结点不再出现在遍历序列的边界、而是出现在遍历序列的中间。这就意味着无论如何我们不能再将根结点作为第一个被 pop 出来的元素来处理了——出栈的时机被改变了，这意味着入栈的逻辑也需要调整。这一次我们不能再通过对 res 动手脚来解决问题，而是需要和 stack 面对面 battle。

中序遍历的序列规则是 左 -> 中 -> 右，这意味着我们必须首先定位到最左的叶子结点。在这个定位的过程中，必然会途径目标结点的父结点、爷爷结点和各种辈分的祖宗结点：

途径过的每一个结点，我们都要及时地把它入栈。这样当最左的叶子结点出栈时，第一个回溯到的就是它的父结点：

有了父结点，就不愁找不到兄弟结点，遍历结果就变得唾手可得了~

基于这个思路，我们来写代码：

编码实现

# 编码复盘

读完这段编码示范，一部分同学可能已经开始懵逼了：看着前面给出的思路分析，似乎完全写不出上面这样的代码啊！所以这段代码到底在干嘛？？？
如果你没有这样的困惑，说明你是一位悟性比较高的同学，可以直接跳过编码复盘部分往下读了（btw给你点个赞~）。

# 层序遍历的衍生问题

题目描述：给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

示例：

返回其层次遍历结果：

示例：

二叉树真题归纳与解读|算法篇

二叉树真题归纳与解读|算法篇