题目
144.二叉树的前序遍历
145.二叉树的后序遍历
94.二叉树的中序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
思路
前序遍历（迭代法）
前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
后序遍历（迭代法）
先序遍历是中左右，后序遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：
中序遍历（迭代法）
在遍历过程中有两个操作：
- 处理：将元素放进result数组中
- 访问：遍历节点
分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
代码
前序遍历
# 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: Optional[TreeNode]) -> List[int]:if not root:return []nums = []stack = [root]while stack:temp = stack.pop()nums.append(temp.val)if temp.right:stack.append(temp.right)if temp.left:stack.append(temp.left)return nums后序遍历
# 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: Optional[TreeNode]) -> List[int]:if not root:return []nums = []stack = [root]while stack:temp = stack.pop()nums.append(temp.val)if temp.left:stack.append(temp.left)if temp.right:stack.append(temp.right)return nums[::-1]中序遍历
# 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: Optional[TreeNode]) -> List[int]:if not root :return []stack =[]result = []cur = rootwhile cur or stack:#cur或者stack中有一个不为空，都一直继续if cur:#如果当前节点不为空的时候，就将当前节点指向该节点的左子树stack.append(cur)cur = cur.leftelse:#如果当前节点为空，那就需要从stack中取出最后一个节点，中序遍历，这个就是中间那个数，再指向右子树cur = stack.pop()result.append(cur.val)cur = cur.rightreturn result
