力扣刷题-二叉树-二叉树的非递归遍历

参考：https://www.programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html#%E6%80%9D%E8%B7%AF

思路

为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？
我们在栈与队列：匹配问题都是栈的强项中提到了，递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。

前序遍历（迭代法）

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
动画如下：

# 迭代法 使用栈实现
class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution(object):def preorderTraversal(self, root): # 传入根节点 为TreeNode类型if not root:return []stack = [root] # 第一个根节点 先存入栈中（因为是中左右的顺序）result = [] # 结果while stack:node = stack.pop() # 从栈内删除该节点并返回该值 上面已经判断过root是否为空result.append(node.val)if node.right: # 注意是nodestack.append(node.right)if node.left:stack.append(node.left)return result

后序遍历（迭代法）

再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：

# 迭代法 使用栈实现
class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution(object):def postorderTraversal(self, root): # 传入根节点 为TreeNode类型if not root:return []stack = [root] # 第一个根节点 先存入栈中（因为是中左右的顺序）result = [] # 结果while stack:node = stack.pop() # 从栈内删除该节点并返回该值 上面已经判断过root是否为空result.append(node.val)if node.left:stack.append(node.left)if node.right: # 注意是nodestack.append(node.right)return result[::-1]

中序遍历

# 迭代法 实现中序遍历
class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution(object):def inorderTraversal(self, root):if not root:return []stack = [] # 注意不能提前加入rootresult = []cur = root # 定义一个当前遍历节点的指针while cur or stack: # 用or# 一路向左if cur:stack.append(cur)cur = cur.left# 到达最左节点 开始处理else:cur = stack.pop() # 删除栈顶的值result.append(cur.val) # 加入至resultcur = cur.rightreturn result