二叉树在面试实战中，花样非常多。本节只是个开头，在后面几个专题、包括最后的大厂真题实战环节中，我们都不会停止对二叉树相关考点的学习和探讨。
在本节，有以下三个命题方向需要大家重点掌握：
- 迭代法实现二叉树的先、中、后序遍历
- 二叉树层序遍历的衍生问题
- 翻转二叉树
这三个方向对应的考题都比较经典。与此同时，解决这些问题涉及到的思路和编码细节，也会成为各位日后解决更加复杂的问题的基石。因此，虽然本节篇幅略长，但还是希望各位能够倾注耐心，给自己充分的时间去理解和消化这些知识。
# “遍历三兄弟”的迭代实现
经过第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]
