Leetcode刷题——10.二叉树遍历

10.二叉树遍历二叉树遍历涉及以特定顺序访问二叉树中的所有节点。先序遍历:根-左-右中序遍历:左-根-右后序遍历:左-右-根【记录路径】核心思想回溯法深度优先搜索 路径回退记录路径的关键是路径入栈访问节点时把节点加入当前路径递归遍历递归遍历左 / 右子树路径出栈回溯递归返回后把节点从当前路径移除避免影响其他分支终止条件到达叶子节点或满足题目条件时保存当前路径的副本。通用模板defrecord_paths(root):# 存储所有符合条件的路径result[]# 存储当前遍历的路径临时path[]defbacktrack(node):ifnotnode:return# 空节点直接返回# 1. 选择将当前节点加入路径path.append(node.val)# 2. 终止条件到达叶子节点无左/右子树ifnotnode.leftandnotnode.right:# 保存路径副本必须用copy否则后续修改会影响已保存的路径result.append(path.copy())else:# 3. 递归遍历左、右子树backtrack(node.left)backtrack(node.right)# 4. 回溯撤销选择移除当前节点关键path.pop()# 从根节点开始回溯backtrack(root)returnresult先序遍历二叉树路径(LeetCode#257)题目描述给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。示例 1输入root [1,2,3,null,5]输出[“1-2-5”,“1-3”]示例 2输入root [1]输出[“1”]提示树中节点的数目在范围 [1, 100] 内-100 Node.val 100题目求解核心思路回溯法深度优先搜索 路径回退# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defbinaryTreePaths(self,root:Optional[TreeNode])-List[str]:result[]path[]defdfs(node):ifnotnode:return# 先存根path.append(node.val)ifnotnode.leftandnotnode.right:# 保存结果result.append(-.join([str(num)fornuminpath]))# 遍历左子树dfs(node.left)# 遍历右子树dfs(node.right)# 回溯移除当前节点path.pop()dfs(root)returnresult中序遍历一二叉搜索树中的第K小元素(LeetCode#230)二叉搜索树 的中序遍历 就是 排好序的题目描述给定一个二叉搜索树的根节点 root 和一个整数 k 请你设计一个算法查找其中第 k 小的元素k 从 1 开始计数。示例 1输入root [3,1,4,null,2], k 1输出1示例 2输入root [5,3,6,2,4,null,null,1], k 3输出3提示树中的节点数为 n 。1 k n 1040 Node.val 104进阶如果二叉搜索树经常被修改插入/删除操作并且你需要频繁地查找第 k 小的值你将如何优化算法题目求解# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defkthSmallest(self,root:Optional[TreeNode],k:int)-int:# 先得到中序遍历结果左 中 右result[]defdfs(node):ifnotnode:returndfs(node.left)result.append(node.val)dfs(node.right)dfs(root)returnresult[k-1]后序遍历二叉树最大路径和(LeetCode#124)题目描述二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root 返回其 最大路径和 。示例 1输入root [1,2,3]输出6解释最优路径是 2 - 1 - 3 路径和为 2 1 3 6示例 2输入root [-10,9,20,null,null,15,7]输出42解释最优路径是 15 - 20 - 7 路径和为 15 20 7 42提示树中节点数目范围是 [1, 3 * 104]-1000 Node.val 1000题目求解# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defmaxPathSum(self,root:Optional[TreeNode])-int:# 后序遍历 左 右 根# 当前节点的路径和左子树路径和 右子树路径和 node.val# 求得 左子树路径和最大值和右子树路径和最大值ansfloat(-inf)defdfs(node):nonlocalans# 声明使用外层 函数的ans变量ifnotnode:return0left_summax(0,dfs(node.left))right_summax(0,dfs(node.right))current_sumleft_sumright_sumnode.val ansmax(ans,current_sum)# 返回当前结果能向上贡献的路径和左子树、或右子树returnnode.valmax(left_sum,right_sum)dfs(root)returnans所有遍历类问题的基础是深度优先搜索DFS 遍历顺序控制不同遍历类型仅调整「访问节点」和「递归子树」的顺序通用框架如下deftraverse(root):ifnotroot:return# 终止条件空节点# 1. 先序位置根→左→右访问当前节点后递归左右子树处理当前节点先序 traverse(root.left)# 2. 中序位置左→根→右递归左子树后访问当前节点再递归右子树处理当前节点中序 traverse(root.right)# 3. 后序位置左→右→根递归完左右子树后访问当前节点处理当前节点后序