1. 题目：
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: # 结果 result = [] # 递归函数 def preorder(node): if node == None: return result.append(node.val) preorder(node.left) preorder(node.right) preorder(root) return result
3. 中序遍历：
# 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 = [] # 递归函数 def inorder(node): if node == None: return inorder(node.left) result.append(node.val) inorder(node.right) inorder(root) return result
4. 后序遍历：
# 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]: # 结果 result = [] # 递归函数 def postorder(node): if node == None: return postorder(node.left) postorder(node.right) result.append(node.val) postorder(root) return result
5. 算法原理
- 确定终止条件：在节点为空时终止
- 搞明白每个遍历的：添加中间节点值、跳转左节点（递归）、跳转右节点（递归），的顺序。
前序遍历是：中左右
中序遍历是：左中右
后序遍历是：左右中
