Leetcode只二叉树中序遍历（python解法）

1.题目描述

示例 1：

输入：root = [1,null,2,3]输出：[1,3,2]

示例 2：

输入：root = []输出：[]

示例 3：

输入：root = [1]输出：[1]

2.解决方法:

中序遍历就是先遍历左子树然后遍历右子树

可以使用栈将左子树所有的根节点的val记录下来，然后在从底部网上遍历，这才是正确的书顺序

此时就可以加上左树和根，此时遍历右子树即可

栈方法：

# 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]:
result = [] # 存放最终遍历结果
stack = [] # 显式栈，模拟递归调用栈
current = root # 当前正在处理的节点，从根开始

# 只要栈不为空，或者当前节点不为空，就继续循环
while stack or current:
# 一路向左，把路径上所有节点压入栈
while current:
stack.append(current)
current = current.left

# 此时 current 为 None，说明已到达最左叶子的左孩子（空）
# 弹出栈顶 —— 这就是当前子树中“最左但未访问”的节点（即该子树的根）
current = stack.pop()
result.append(current.val) # 访问它（加入结果）

# 转向它的右子树（可能为空，也可能有内容）
current = current.right

return result

递归方法：

def inorderTraversal(root):
if not root: # 基础情况
return []

left_list = inorderTraversal(root.left) # 递归处理左子树
right_list = inorderTraversal(root.right) # 递归处理右子树

return left_list + [root.val] + right_list