【树】力扣144：二叉树的前序遍历（附中序后序层序）
输入一个二叉树，输出一个数组，为二叉树前序遍历的结果。
示例：
输入：root = [1,null,2,3]
输出：[1,2,3]
二叉树遍历题目：
114. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
102. 二叉树的层序遍历
递归
递归的本质是栈的调用。
递归的模板相对比较固定，一般都会新增一个 dfs 函数：
def dfs(root):
if not root:
return None
res.append(root.val) # 前序遍历
dfs(root.left)
dfs(root.right)
对于前序、中序和后序遍历，只需将递归函数里的 res.append(root.val) 放在不同位置即可，然后在主函数中调用这个递归函数就可以了，代码完全一样。
前序
-
base case: 空树，即根结点为空
-
重复的子问题：先取根结点，再遍历左子树，最后遍历右子树
-
终止条件：当前结点为空
定义辅函数 preorder(node) 表示当前遍历到 node 结点的结果集。先将 node 结点的值加入结果集，然后递归调用 preorder(node.left) 来遍历 node 结点的左子树，再递归调用 preorder(node.right) 来遍历 node 结点的右子树。递归终止的条件为结点为空。
# 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: # base case
return []
res = []
def preorder(node):
if not node: # 递归终止条件
return None
res.append(node.val) # 将 node 结点的值加入结果集
preorder(node.left) # 遍历 node 结点的左子树
preorder(node.right) # 遍历 node 结点的右子树
preorder(root)
return res
单独辅函数版本，注意self：
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.preorder(root)
def preorder(self, root): # 加上 self
if root == None:
return
res.append(root.val)
self.preorder(root.left)
self.preorder(root.right)
时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。
中序
遍历顺序：左孩子 -> 根结点 -> 右孩子
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(root):
if not root:
return None
dfs(root.left)
res.append(root.val)
dfs(root.right)
dfs(root)
return res
后序
遍历顺序：左孩子 -> 右孩子 -> 根结点
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(root):
if not root:
return None
dfs(root.left)
dfs(root.right)
res.append(root.val)
dfs(root)
return res
迭代
递归是隐式地维护了一个栈，在迭代的时候就需要显式地将这个栈模拟出来。
迭代法就是不断地将旧的变量值，递推计算新的变量值。
前序
1. 常规解法
前序遍历的顺序是 根结点、左子树、右子树，也就是 先输出根结点，再输出左子树，最后输出右子树。
由于栈 “先入后出” 的特点，所以结合前序遍历的顺序，迭代的过程就是：每次都先将根结点放入栈，然后是右子树和左子树。
-
初始化维护一个栈 stack，先将根结点 root 入栈
stack = [root] -
当栈不为空时
- 弹出栈顶元素 node，将 node 结点的值加入结果集 res 中
node = stack.pop() res.append(node.val)- 若 node 的右子树不为空，右子树入栈
if node.right: stack.append(node.right)- 若 node 的左子树不为空，左子树入栈
if node.left: stack.append(node.left)
总体代码：
能够理解循环内的 node 不是 树的 root，也可以把 node 写为 root，在循环内这只是一个变量。
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack, res = [root], []
while stack:
node = stack.pop()
if node:
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个结点恰好被遍历一次。
空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。
2. 模板解法
模板解法的思路稍有不同：
-
先将根结点 cur 和所有的左孩子入栈，并加入到结果集中，直至 cur 为空，用一个 while 循环实现
-
然后，每弹出一个栈顶元素 tmp，就到达它的右孩子，再将这个结点当作 cur 重新按上面的步骤来一遍，直至栈为空。这里又需要一个 while 循环
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
cur, stack, res = root, [], []
while cur or stack:
while cur: # 根结点和所有左孩子入栈
stack.append(cur)
res.append(cur.val)
cur = cur.left
tmp = stack.pop() # 每弹出一个元素，就到达其右孩子
cur = tmp.right
return res
中序
和前序遍历的代码完全相同，只是在出栈的时候才将节点 tmp 的值加入到结果中。
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
cur, stack, res = root, [], []
while cur or stack:
while cur: # cur 入栈，并到达最左端的叶子结点
stack.append(cur)
cur = cur.left
tmp = stack.pop()
res.append(tmp.val) # 出栈时再加入结果 tmp.val
cur = tmp.right
return res
后序
-
结点 cur 先到达最右端的叶子节点，并将路径上的结点入栈。
-
每次从栈中弹出一个元素后，cur 到达它的左孩子，并将左孩子看作 cur 继续执行上面的步骤。
-
最后将结果反向输出即可。
总体来讲就是和前序遍历的左右相反。
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
cur, stack, res = root, [], []
while cur or stack:
while cur: # 先到达最右端
res.append(cur.val)
stack.append(cur)
cur = cur.right
tmp = stack.pop()
cur = tmp.left
return res[::-1] # 反向输出