本文参考labuladongsuanfa笔记[【强化练习】用「遍历」思维解题 II | labuladong 的算法笔记]
如果让你在二叉树中的某些节点上做文章，一般来说也可以直接用遍历的思维模式。
270. 最接近的二叉搜索树值 | 力扣 | LeetCode |
给你二叉搜索树的根节点 root 和一个目标值 target ，请在该二叉搜索树中找到最接近目标值 target 的数值。如果有多个答案，返回最小的那个。
示例 1：
输入：root = [4,2,5,1,3], target = 3.714286 输出：4
示例 2：
输入：root = [1], target = 4.428571 输出：1
提示：
- 树中节点的数目在范围
[1, 104]内 0 <= Node.val <= 109-109 <= target <= 109
基本思路
前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题需要用到「遍历」的思维。
我们遍历 BST，施展 700. 二叉搜索树中的搜索 的解法在 BST 中搜索 target，甭管能不能搜索到，一边搜索一边更新最接近 target 的值即可。
class Solution:def __init__(self):self.res = float('inf')def closestValue(self, root: TreeNode, target: float) -> int:self.traverse(root, target)return self.res# 遍历函数，在 BST 中搜索 target# 我们在中序位置写 if 判断逻辑，这样就可以从小到大执行，保证最终结果是值最小的def traverse(self, root: TreeNode, target: float) -> None:if root is None:return# 根据 target 和 root.val 的相对大小决定去左右子树搜索if root.val < target:# 中序位置（左子树遍历结束，准备遍历右子树时）if abs(root.val - target) < abs(self.res - target):self.res = root.val# 如果 target 比 root 大，那么 root 的左子树差值肯定更大，直接遍历右子树self.traverse(root.right, target)else:# 如果 target 比 root 小，那么 root 的右子树差值肯定更大，直接遍历左子树self.traverse(root.left, target)# 中序位置（左子树遍历结束，准备遍历右子树时）if abs(root.val - target) < abs(self.res - target):self.res = root.val
404. 左叶子之和 | 力扣 | LeetCode |
给定二叉树的根节点 root ，返回所有左叶子之和。
示例 1：
输入: root = [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
示例 2:
输入: root = [1] 输出: 0
提示:
- 节点数在
[1, 1000]范围内 -1000 <= Node.val <= 1000
class Solution:def __init__(self):self.sum = 0# 记录左叶子之和# int sum = 0; # This is handled in the constructor now# 二叉树遍历函数def traverse(self, root):if root is None:returnif root.left is not None and \root.left.left is None and root.left.right is None:# 找到左侧的叶子节点，记录累加值self.sum += root.left.val# 递归框架self.traverse(root.left)self.traverse(root.right)def sumOfLeftLeaves(self, root: TreeNode) -> int:self.traverse(root)return self.sum623. 在二叉树中增加一行 | 力扣 | LeetCode |
给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。
注意，根节点 root 位于深度 1 。
加法规则如下:
- 给定整数
depth，对于深度为depth - 1的每个非空树节点cur，创建两个值为val的树节点作为cur的左子树根和右子树根。 cur原来的左子树应该是新的左子树根的左子树。cur原来的右子树应该是新的右子树根的右子树。- 如果
depth == 1意味着depth - 1根本没有深度，那么创建一个树节点，值val作为整个原始树的新根，而原始树就是新根的左子树。
示例 1:
输入: root = [4,2,6,3,1,5], val = 1, depth = 2 输出: [4,1,1,2,null,null,6,3,1,5]
示例 2:
输入: root = [4,2,null,3,1], val = 1, depth = 3 输出: [4,2,null,1,1,3,null,null,1]
提示:
- 节点数在
[1, 104]范围内 - 树的深度在
[1, 104]范围内 -100 <= Node.val <= 100-105 <= val <= 1051 <= depth <= the depth of tree + 1
class Solution:def __init__(self):self.targetVal = 0self.targetDepth = 0def addOneRow(self, root: TreeNode, val: int, depth: int) -> TreeNode:self.targetVal = valself.targetDepth = depth# 插入到第一行的话特殊对待一下if self.targetDepth == 1:newRoot = TreeNode(self.targetVal)newRoot.left = rootreturn newRoot# 遍历二叉树，走到对应行进行插入self.traverse(root, 1)return rootdef traverse(self, root: TreeNode, curDepth: int):if root is None:return# 前序遍历if curDepth == self.targetDepth - 1:# 进行插入newLeft = TreeNode(self.targetVal)newRight = TreeNode(self.targetVal)newLeft.left = root.leftnewRight.right = root.rightroot.left = newLeftroot.right = newRight# Recursively traverse the left and right subtreeself.traverse(root.left, curDepth + 1)self.traverse(root.right, curDepth + 1)
971. 翻转二叉树以匹配先序遍历 | 力扣 | LeetCode |
给你一棵二叉树的根节点 root ，树中有 n 个节点，每个节点都有一个不同于其他节点且处于 1 到 n 之间的值。
另给你一个由 n 个值组成的行程序列 voyage ，表示 预期 的二叉树 先序遍历 结果。
通过交换节点的左右子树，可以 翻转 该二叉树中的任意节点。例，翻转节点 1 的效果如下：
请翻转 最少 的树中节点，使二叉树的 先序遍历 与预期的遍历行程 voyage 相匹配 。
如果可以，则返回 翻转的 所有节点的值的列表。你可以按任何顺序返回答案。如果不能，则返回列表 [-1]。
示例 1：
输入：root = [1,2], voyage = [2,1] 输出：[-1] 解释：翻转节点无法令先序遍历匹配预期行程。
示例 2：
输入：root = [1,2,3], voyage = [1,3,2] 输出：[1] 解释：交换节点 2 和 3 来翻转节点 1 ，先序遍历可以匹配预期行程。
示例 3：
输入：root = [1,2,3], voyage = [1,2,3] 输出：[] 解释：先序遍历已经匹配预期行程，所以不需要翻转节点。
提示：
- 树中的节点数目为
n n == voyage.length1 <= n <= 1001 <= Node.val, voyage[i] <= n- 树中的所有值 互不相同
voyage中的所有值 互不相同
用 traverse 函数遍历整棵二叉树，对比前序遍历结果，如果节点的值对不上，就无解；如果子树对不上 voyage，就尝试翻转子树。
class Solution:def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:self.res = []self.i = 0self.can_flip = Truedef dfs(node):# 遍历的过程中尝试进行反转if not node or not self.can_flip:return Trueif node.val != voyage[self.i]:# 节点的 val 对不上，必然无解self.can_flip = Falsereturn Falseself.i += 1# Only flip if there's a left child and the next value in voyage doesn't match the left child's valueif node.left and node.left.val != voyage[self.i]:# 前序遍历结果不对，尝试翻转左右子树self.res.append(node.val)node.left, node.right = node.right, node.left# 记录翻转节点# Note: This comment was not in the original Java code, but added to match the pattern of comments. # If this was not intended, it can be removed.return dfs(node.left) and dfs(node.right)if dfs(root):return self.reselse:return [-1]
987. 二叉树的垂序遍历 | 力扣 | LeetCode |
给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。
对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。
二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。
返回二叉树的 垂序遍历 序列。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[9],[3,15],[20],[7]] 解释： 列 -1 ：只有结点 9 在此列中。 列 0 ：只有结点 3 和 15 在此列中，按从上到下顺序。 列 1 ：只有结点 20 在此列中。 列 2 ：只有结点 7 在此列中。
示例 2：
输入：root = [1,2,3,4,5,6,7] 输出：[[4],[2],[1,5,6],[3],[7]] 解释： 列 -2 ：只有结点 4 在此列中。 列 -1 ：只有结点 2 在此列中。 列 0 ：结点 1 、5 和 6 都在此列中。1 在上面，所以它出现在前面。5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。 列 1 ：只有结点 3 在此列中。 列 2 ：只有结点 7 在此列中。
示例 3：
输入：root = [1,2,3,4,6,5,7] 输出：[[4],[2],[1,5,6],[3],[7]] 解释： 这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。 因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。
提示：
- 树中结点数目总数在范围
[1, 1000]内 0 <= Node.val <= 1000
看这题的难度是困难，但你别被吓住了，我们从简单的开始，如果以整棵树的根节点为坐标 (0, 0)，你如何打印出其他节点的坐标？
很简单，写出如下代码遍历一遍二叉树即可：
void traverse(TreeNode root, int row, int col) {if (root == null) {return;}print(row, col);traverse(root.left, row + 1, col - 1);traverse(root.right, row + 1, col + 1);
}然后就简单了，把这些坐标收集起来，依据题目要求进行排序，组装成题目要求的返回数据格式即可。
class Solution:# 记录每个节点和对应的坐标 (row, col)class Triple:def __init__(self, node, row, col):self.node = nodeself.row = rowself.col = coldef verticalTraversal(self, root: TreeNode) -> List[List[int]]:# 遍历二叉树，并且为所有节点生成对应的坐标self.traverse(root, 0, 0)# 根据题意，根据坐标值对所有节点进行排序：# 按照 col 从小到大排序，col 相同的话按 row 从小到大排序，# 如果 col 和 row 都相同，按照 node.val 从小到大排序。self.nodes.sort(key=lambda x: (x.col, x.row, x.node.val))# 将排好序的节点组装成题目要求的返回格式res = collections.deque()# 记录上一列编号，初始化一个特殊值preCol = float('-inf')for cur in self.nodes:if cur.col != preCol:# 开始记录新的一列res.append(collections.deque())preCol = cur.colres[-1].append(cur.node.val)return [list(col) for col in res]def __init__(self):self.nodes = []# 二叉树遍历函数，记录所有节点对应的坐标def traverse(self, root: TreeNode, row: int, col: int):if root is None:return# 记录坐标self.nodes.append(self.Triple(root, row, col))# 二叉树遍历框架self.traverse(root.left, row + 1, col - 1)self.traverse(root.right, row + 1, col + 1)tips
1、关于 Triple 对象，写成内部类和外部类在新建对象的时候表示方法不同，注意区别。
2、res = collections.deque() 就是新建一个双端队列，注意尾部的括号（） 别掉。
3、整体思路就是先遍历整颗树，把每个节点的行坐标和列坐标记录下来，然后对其排序（优先级：列>行>值）。
4、最后把排好序的self.nodes根据列坐标依次添加到res队列中，最后再将队列转化为List返回即可。
993. 二叉树的堂兄弟节点 | 力扣 | LeetCode |
在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
示例 1：
输入：root = [1,2,3,4], x = 4, y = 3 输出：false
示例 2：
输入：root = [1,2,3,null,4,null,5], x = 5, y = 4 输出：true
示例 3：
输入：root = [1,2,3,null,4], x = 2, y = 3 输出：false
提示：
- 二叉树的节点数介于
2到100之间。 - 每个节点的值都是唯一的、范围为
1到100的整数。
遍历找到 x，y 的深度和父节点，对比即可。
class Solution:def __init__(self):self.parentX = Noneself.parentY = Noneself.depthX = 0self.depthY = 0self.x = 0self.y = 0def isCousins(self, root: TreeNode, x: int, y: int) -> bool:self.x = xself.y = yself.traverse(root, 0, None)if self.depthX == self.depthY and self.parentX != self.parentY:# 判断 x，y 是否是表兄弟节点return Truereturn Falsedef traverse(self, root: TreeNode, depth: int, parent: TreeNode) -> None:if root is None:returnif root.val == self.x:# 找到 x，记录它的深度和父节点self.parentX = parentself.depthX = depthif root.val == self.y:# 找到 y，记录它的深度和父节点self.parentY = parentself.depthY = depthself.traverse(root.left, depth + 1, root)self.traverse(root.right, depth + 1, root)1315. 祖父节点值为偶数的节点和 | 力扣 | LeetCode |
给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：
- 该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）
如果不存在祖父节点值为偶数的节点，那么返回 0 。
示例：
输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] 输出：18 解释：图中红色节点的祖父节点的值为偶数，蓝色节点为这些红色节点的祖父节点。
提示：
- 树中节点的数目在
1到10^4之间。 - 每个节点的值在
1到100之间。
class Solution:def __init__(self):self.sum = 0def sumEvenGrandparent(self, root: TreeNode) -> int:self.traverse(root)return self.sum# 二叉树的遍历函数def traverse(self, root: TreeNode):if root is None:returnif root.val % 2 == 0:# 累加左子树孙子节点的值if root.left is not None:if root.left.left is not None:self.sum += root.left.left.valif root.left.right is not None:self.sum += root.left.right.val# 累加右子树孙子节点的值if root.right is not None:if root.right.left is not None:self.sum += root.right.left.valif root.right.right is not None:self.sum += root.right.right.val# 二叉树的遍历框架self.traverse(root.left)self.traverse(root.right)
1448. 统计二叉树中好节点的数目 | 力扣 | LeetCode |
给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。
「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
示例 1：
输入：root = [3,1,4,3,null,1,5] 输出：4 解释：图中蓝色节点为好节点。 根节点 (3) 永远是个好节点。 节点 4 -> (3,4) 是路径中的最大值。 节点 5 -> (3,4,5) 是路径中的最大值。 节点 3 -> (3,1,3) 是路径中的最大值。
示例 2：
输入：root = [3,3,null,4,2] 输出：3 解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。
示例 3：
输入：root = [1] 输出：1 解释：根节点是好节点。
提示：
- 二叉树中节点数目范围是
[1, 10^5]。 - 每个节点权值的范围是
[-10^4, 10^4]。
class Solution:def __init__(self):self.count = 0def goodNodes(self, root: TreeNode) -> int:self.traverse(root, root.val)return self.count# 二叉树遍历函数，pathMax 参数记录从根节点到当前节点路径中的最大值def traverse(self, root: TreeNode, pathMax: int):if root is None:returnif pathMax <= root.val:# 找到一个「好节点」self.count += 1# 更新路径上的最大值pathMax = max(pathMax, root.val)self.traverse(root.left, pathMax)self.traverse(root.right, pathMax)1469. 寻找所有的独生节点 | 力扣 | LeetCode |
二叉树中，如果一个节点是其父节点的唯一子节点，则称这样的节点为 “独生节点” 。二叉树的根节点不会是独生节点，因为它没有父节点。
给定一棵二叉树的根节点 root ，返回树中 所有的独生节点的值所构成的数组 。数组的顺序 不限 。
示例 1：
输入：root = [1,2,3,null,4] 输出：[4] 解释：浅蓝色的节点是唯一的独生节点。 节点 1 是根节点，不是独生的。 节点 2 和 3 有共同的父节点，所以它们都不是独生的。
示例 2：
输入：root = [7,1,4,6,null,5,3,null,null,null,null,null,2] 输出：[6,2] 输出：浅蓝色的节点是独生节点。 请谨记，顺序是不限的。 [2,6] 也是一种可接受的答案。
示例 3：
输入：root = [11,99,88,77,null,null,66,55,null,null,44,33,null,null,22] 输出：[77,55,33,66,44,22] 解释：节点 99 和 88 有共同的父节点，节点 11 是根节点。 其他所有节点都是独生节点。
提示：
tree中节点个数的取值范围是[1, 1000]。1 <= Node.val <= 106
class Solution:def getLonelyNodes(self, root: TreeNode) -> List[int]:self.res = []self.traverse(root, False)return self.res# 二叉树遍历函数def traverse(self, root: TreeNode, is_root: bool) -> None:if root is None:return# 发现独生节点# Only add the child node if it is a lonely node (has no sibling and is not the root node)if not is_root:if (root.left is None and root.right is not None) or (root.left is not None and root.right is None):self.res.append(root.left.val) if root.left else self.res.append(root.right.val)# 二叉树遍历框架# Recursively traverse the left and right children, the second parameter is False now because we are going deeperself.traverse(root.left, False)self.traverse(root.right, False)1602. 找到二叉树中最近的右侧节点 | 力扣 | LeetCode |
给定一棵二叉树的根节点 root 和树中的一个节点 u ，返回与 u 所在层中距离最近的右侧节点，当 u 是所在层中最右侧的节点，返回 null 。
示例 1：
输入：root = [1,2,3,null,4,5,6], u = 4 输出：5 解释：节点 4 所在层中，最近的右侧节点是节点 5。
示例 2：
输入：root = [3,null,4,2], u = 2 输出：null 解释：2 的右侧没有节点。
示例 3：
输入：root = [1], u = 1 输出：null
示例 4：
输入：root = [3,4,2,null,null,null,1], u = 4 输出：2
提示:
- 树中节点个数的范围是
[1, 105]。 1 <= Node.val <= 105- 树中所有节点的值是唯一的。
u是以root为根的二叉树的一个节点。
这道题的直接思路是用 BFS 层序遍历算法，肯定可以找到节点 u 的相邻节点。
如果你熟悉二叉树的前中后序遍历的顺序，就知道前序遍历也可以找到 u 的相邻节点：
先找到 u 的层数 targetDepth，然后再次走到 targetDepth 时遇到的就是 u 的相邻节点。
class Solution:def findNearestRightNode(self, root: TreeNode, u: TreeNode) -> TreeNode:self.targetDepth = -1self.res = Noneself.traverse(root, 0, u.val)return self.res# 二叉树遍历函数def traverse(self, root: TreeNode, depth: int, targetVal: int) -> None:if not root or self.res:returnif targetVal == root.val:# 找到目标层数self.targetDepth = depthelif depth == self.targetDepth:# 找到下一个当前层数的节点self.res = rootreturn# 二叉树遍历框架self.traverse(root.left, depth + 1, targetVal)self.traverse(root.right, depth + 1, targetVal)
