给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[2,1]
示例 5：
输入：root = [1,null,2] 输出：[1,2]
示例代码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]:
flag1, flag2 = 0, 1
res = []
stack = [(flag1, root)]
while stack:
flag, node = stack.pop()
if node is None:
continue
if flag == flag1:
stack.append((flag1, node.right))
stack.append((flag2, node))
stack.append((flag1, node.left))
else:
res.append(node.val)
return res
思路解析：
- 使用flag标记每个节点的状态，新节点标记为flag1，已经访问过的标记为flag2。
- 如果遇到节点为flag1，则将标记改为flag2，然后将其右子节点、自身和左子节点依次进栈。
- 如果遇到节点为flag2，则将节点直接输出。
注意：
- 如要实现前序、后序遍历，只需要调整左右子节点的入栈顺序即可。
标记法迭代（需要双倍的空间来存储访问状态）：
- 前、中、后、层序通用模板，只需改变进栈顺序或即可实现前后中序遍历，
- 而层序遍历则使用队列先进先出。0表示当前未访问，1表示已访问。
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = [(0, root)]
while stack:
flag, cur = stack.pop()
if not cur:
continue
if flag == 0:
# 前序，标记法
stack.append((0, cur.right))
stack.append((0, cur.left))
stack.append((1, cur))
# # 后序，标记法
# stack.append((1, cur))
# stack.append((0, cur.right))
# stack.append((0, cur.left))
# # 中序，标记法
# stack.append((0, cur.right))
# stack.append((1, cur))
# stack.append((0, cur.left))
else:
res.append(cur.val)
return res
# # 层序，标记法
# res = []
# queue = [(0, root)]
# while queue:
# flag, cur = queue.pop(0) # 注意是队列，先进先出
# if not cur: continue
# if flag == 0:
# 层序遍历这三个的顺序无所谓，因为是队列，只弹出队首元素
# queue.append((1, cur))
# queue.append((0, cur.left))
# queue.append((0, cur.right))
# else:
# res.append(cur.val)
# return res
示例代码2：【递归】
# 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 []
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
# 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 []
ret = []
def dfs(root):
if root.left is not None:
dfs(root.left)
ret.append(root.val)
if root.right is not None:
dfs(root.right)
dfs(root)
return ret
def preorderTraversal(self, root):
if not root:
return []
# 前序递归
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
# # 中序递归
# return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
# # 后序递归
# return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]时间复杂度：
- 时间复杂度：O(n)，n为节点数，访问每个节点恰好一次。
- 空间复杂度：空间复杂度：O(h)，h为树的高度。最坏情况下需要空间O(n)，平均情况为O(logn）
递归通用模板，可以适应不同的题目，添加参数、增加返回条件、修改进入递归条件、自定义返回值：
def preorderTraversal(self, root):
def dfs(cur):
if not cur:
return
# 前序递归
res.append(cur.val)
dfs(cur.left)
dfs(cur.right)
# # 中序递归
# dfs(cur.left)
# res.append(cur.val)
# dfs(cur.right)
# # 后序递归
# dfs(cur.left)
# dfs(cur.right)
# res.append(cur.val)
res = []
dfs(root)
return res
本地代码实现：
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
# create a tree
def create_tree(self, nums, index):
if not nums:
return None
if index >= len(nums):
return None
root = TreeNode(nums[index])
root.left = self.create_tree(nums, index * 2 + 1)
root.right = self.create_tree(nums, index * 2 + 2)
return root
def preorderTraversal(self, root):
if not root:
return []
return [root.val] + self.inorderTraversal(root.left) + self.inorderTraversal(root.right)
def inorderTraversal(self, root):
if not root:
return []
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
def posorderTraversal(self, root):
if not root:
return []
return self.inorderTraversal(root.left) + self.inorderTraversal(root.right) + [root.val]
lst = [1, 2, 3]
obj = Solution()
ret = obj.create_tree(lst, 0)
pre_order = obj.preorderTraversal(ret)
print('先序遍历：', pre_order)
in_order = obj.inorderTraversal(ret)
print('中序遍历：', in_order)
pos_order = obj.posorderTraversal(ret)
print('后序遍历：', pos_order)
运行结果：
