不会还有人不会写非递归的二叉树遍历吧？
大家好呀，今天的我还是在爬二叉树的帅蛋。
二叉树的前中后序遍历有两种实现方式：递归和非递归。上篇文章讲了递归法：
那今天就来看非递归版的二叉树前中后序遍历怎么整。
非递归的做法，很多人又叫迭代法。迭代法就是不断地将旧的变量值，递推计算新的变量值。
迭代法是怎么做呢？不卖关子，是用栈来做。
我简单给大家讲一下为什么可以用“栈”。
这个其实还是因为二叉树的前中后序遍历能用“递归”。举一个简单点的例子，下面的图是一个递归函数的运作：
我想求 f(3)，就得知道 f(2)，那 f(2) 怎么求，当然得知道 f(1) 是啥...
你看我最先想要求的数，反而是最后才知道。
你有没有觉得这个和“我最先进去的数，反而是最后才出来”很像？这个先入后出，不就正是“栈”嘛！
没错，递归问题的处理，可以用栈来解决。
破案了！递归的时候竟然是隐式的维护了一个栈！没想到你竟是这样的递归！
那我们把这个栈光明正大的模拟出来就是迭代法了。
请喊我大聪明。
如果有小婊贝还不知道栈是个什么玩意儿，麻烦先来一句“蛋蛋真帅”，再看下文：
接下来，直接开整！
我还是用三道 题来给大家具体讲解二叉树前中后序遍历的非递归版。
这篇是我在牛客网连载系列 #帅蛋的数据结构与算法空间#的第 12 篇文章，欢迎大家关注。
也希望大家能够喜欢上帅蛋，多多点赞收藏，记得关注我呀！
二叉树前序遍历（非递归版）
二叉树的前序遍历
给你二叉树根节点 root，返回它节点值的前序遍历。
示例
输入：root = [1,null,2,3]
输出：[1,2,3]
解析
前序遍历的非递归版本大概是最好写的一个了。
都知道前序遍历的顺序是：根、左子树、右子树，也就是先输出根，再输出左子树，最后输出右子树。
因为栈“先入后出”的特点，所以结合前序遍历的顺序，迭代的过程也就出来了：
每次都是先将根节点放入栈，然后右子树，最后左子树。
具体步骤如下所示：
初始化维护一个栈，将根节点入栈。
当栈不为空时
- 弹出栈顶元素 node，将节点值加入结果数组中。
- 若 node 的右子树不为空，右子树入栈。
- 若 node 的左子树不为空，左子树入栈。
图解
以下图为例：
首先初始化一个栈，将根节点入栈。
stack = [root]
栈不为空，根节点出栈，将节点值加入结果数组中。
# 根节点出栈 node = stack.pop() # 将根节点值加入结果 res.append(node.val)
接下来的顺序就是，右子树入栈，左子树入栈，弹出栈顶元素。
while stack:
# 根节点出栈
node = stack.pop()
# 将根节点值加入结果
res.append(node.val)
# 右子树入栈
if node.right:
stack.append(node.right)
# 左子树入栈
if node.left:
stack.append(node.left)
直至栈为空，返回结果。
此解法，由于每个节点被遍历一次，所以时间复杂度为 O(n)。
额外维护了一个栈，空间复杂度为 O(n)。
代码实现
Python 代码实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
# 注意：根节点为空，直接返回空列表
if not root:
return []
stack = [root]
res = []
while stack:
# 根节点出栈
node = stack.pop()
# 将根节点值加入结果
res.append(node.val)
# 右子树入栈
if node.right:
stack.append(node.right)
# 左子树入栈
if node.left:
stack.append(node.left)
return res
Java 代码实现
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
ArrayList<Integer> res = new ArrayList<>();
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(node.val);
if(node.right != null) {
stack.push(node.right);
}
if(node.left != null) {
stack.push(node.left);
}
}
return res;
}
}
二叉树中序遍历（非递归版）
二叉树的中序遍历
给你二叉树根节点 root，返回它的中序遍历。
示例
输入：root = [1,null,2,3]
输出：[1,3,2]
解析
中序遍历的非递归就没前序遍历那么好搞了。
前序遍历是先搞根节点，再去管左子树，右子树，这就意味着，在前序遍历中你遍历节点的顺序和你处理节点的顺序是一致的。
这句话你要仔细品，很重要。
而中序遍历的顺序是：左子树、根、右子树，先输出左子树，再输出根节点，最后输出右子树。
这就意味着，在中序遍历中，访问节点的顺序和处理节点的顺序是不一致的，并且，处理节点是在遍历完左子树之后。
再直白点就是：从根节点开始，一层层的遍历，找到左子树最左的那个节点，从它开始处理节点。
例如下图中的 H 节点。
具体步骤如下所示：
初始化一个空栈。
当【根节点不为空】或者【栈不为空】时，从根节点开始
- 若当前节点有左子树，一直遍历左子树，每次将当前节点压入栈中。
- 若当前节点无左子树，从栈中弹出该节点，尝试访问该节点的右子树。
图解
以下图为例：
首先初始化一个空栈。
stack = []
从根节点开始，一直向左子树遍历，同时将当前的节点压入栈中。
# 一直向左子树走，每一次将当前节点保存到栈中
if root:
stack.append(root)
root = root.left
当前走到了最左面，弹出栈顶元素，加入结果数组中。
if not root:
cur = stack.pop()
res.append(cur.val)
root = cur.right
节点 2 并无右子树，继续重复上述动作。
此时节点 0 有右子树，遍历其右子树，遍历到的节点入栈。
接下来的动作就是在重复上面的操作。
直至 root 无指向而且栈为空，返回结果。
此解法，由于每个节点被遍历一次，所以时间复杂度为 O(n)。
额外维护了一个栈，空间复杂度为 O(n)。
代码实现
Python 代码实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
# 注意：根节点为空，直接返回空列表
if not root:
return []
stack = []
res = []
while root or stack:
# 一直向左子树走，每一次将当前节点保存到栈中
if root:
stack.append(root)
root = root.left
# 当前节点为空，证明走到了最左边，从栈中弹出节点加入结果数组
# 开始对右子树重复上述过程。
else:
cur = stack.pop()
res.append(cur.val)
root = cur.right
return res
Java 代码实现
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null){
return new int[]
}
List<Integer> res = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
while(stack.size() > 0 || root != null) {
if(root != null) {
stack.add(root);
root = root.left;
}
else {
TreeNode cur = stack.pop();
res.add(cur.val);
root = cur.right;
}
}
return res;
}
}
二叉树后序遍历（非递归版）
二叉树的后序遍历
给定一个二叉树，返回它的后序遍历。
示例
输入：root = [1,null,2,3]
输出：[3,2,1]
解析
恭喜你，越过非递归的前序遍历和中序遍历，来到后续遍历。
非递归版的后续遍历是三种遍历中最复杂的一个，当然啦，只是相比而言，也不是那么复杂。
我就不卖关子了，直接说怎么整。
后序遍历的顺序是：左子树、右子树、根，先输出左子树，再输出右子树，最后输出根。
那对于根节点来说，它要被搞 3 次：
- 第 1 次经过它，去向左子树。
- 第 2 次从左子树回来，经过它，去向右子树。
- 第 3 次从右子树回退到它。
具体步骤如下所示：
初始化一个空栈。
当【根节点不为空】或者【栈不为空】时，从根节点开始
- 每次将当前节点压入栈中，如果当前节点右左子树，就往左子树跑，没有左子树就往右子树跑。
- 若当前节点无左子树也无右子树，从栈中弹出该节点，如果当前节点是上一个节点（即弹出该节点后的栈顶元素）的左节点，尝试访问上个节点的右子树，如果不是，那当前栈的栈顶元素继续弹出。
图解
以下图为例：
首先初始化一个空栈。
stack = []
从根节点开始，如果当前节点一直有左子树，那就一直向左子树遍历，同时将当前的节点压入栈中。
while root:
# 当前节点入栈
stack.append(root)
# 如果当前节点有左子树，继续向左子树找
if root.left:
root = root.left
当前走到了最左面，当前栈顶元素无左右子树，为叶子节点，弹出栈顶元素，加入结果数组中。
# 跳出循环的条件是 root 为空，那当前栈顶元素为叶子节点。 # 弹出栈顶元素，并加入结果数组 cur = stack.pop() res.append(cur.val)
当前 cur 为 当前栈顶元素的左节点，继续遍历当前栈顶元素的右子树。
if stack and stack[-1].left == cur:
root = stack[-1].right
接下来的动作就是在重复上面的操作。
本题解同样时间复杂度为 O(n)，空间复杂度为 O(n)。
代码实现
Python 代码实现
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
# 注意：根节点为空，直接返回空列表
if not root:
return []
stack = []
res = []
while root or stack:
while root:
# 当前节点入栈
stack.append(root)
# 如果当前节点有左子树，继续向左子树找
if root.left:
root = root.left
# 如果当前节点无左子树，在右子树继续找
else:
root = root.right
# 跳出循环的条件是 root 为空，那当前栈顶元素为叶子节点。
# 弹出栈顶元素，并加入结果数组
cur = stack.pop()
res.append(cur.val)
# 如果栈不为空，且当前栈顶元素的左节点是刚刚跳出的栈顶元素 cur
# 则转向遍历右子树当前栈顶元素的右子树
if stack and stack[-1].left == cur:
root = stack[-1].right
# 否则证明当前栈顶元素无左右子树，那当前的栈顶元素弹出。
else:
root = None
return res
Java 代码实现
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
while(!stack.isEmpty() || root != null){
while(root != null){
stack.addLast(root);
if(root.left != null){
root = root.left;
}
else{
root = root.right;
}
}
root = stack.removeLast();
res.add(root.val);
if(!stack.isEmpty() && stack.getLast().left == root){
root = stack.getLast().right;
}
else{
root = null;
}
}
return res;
}
}
哎呀妈呀，到这，二叉树前中后续遍历（非递归版）终于算是写完了。
自认为已经将三种遍历的非递归法讲明白了，跟着一步步的走下来，绝对没问题。
从无到有的过程很辛苦，无所不能的样子又很酷。
大家加油~
❤️ 欢迎关注我，有问题，找帅蛋，我最看不得别人迷茫！
❤️ 如果你觉得有帮助,希望爱学习的你不要吝啬三连击哟[点赞 + 收藏 + 评论]~
还有小小公众号 【编程文青李狗蛋】，聊聊迷茫吹吹牛皮~
- 数据结构与算法作为计算机学生最重要的课程之一，不管是面试或者考研都是重中之重，不应该让这个成为同学们的困扰。 - 站在初学者的角度，用最直白的图解和最易懂的代码，最大可能摒除不同编程语言的带来的干扰，带你彻底搞定数据结构与算法。 - 本专栏适用于任何想要学习数据结构与算法的未来巨巨~
