【leetcode练习·二叉树】用「遍历」思维解题 I
本文参考labuladong算法笔记[【强化练习】用「遍历」思维解题 I | labuladong 的算法笔记]
257. 二叉树的所有路径 | 力扣 | LeetCode |
给你一个二叉树的根节点 root
,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"]
示例 2:
输入:root = [1] 输出:["1"]
提示:
- 树中节点的数目在范围
[1, 100]
内 -100 <= Node.val <= 100
前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式,这道题需要用到「遍历」的思维。
你让我求所有根节点到叶子节点的路径,那我遍历一遍二叉树肯定可以搞定,遍历到叶子节点的时候想办法把路径生成出来就行了。
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
# 遍历一遍二叉树就能出结果了
self.traverse(root)
return self.res
def __init__(self):
# 记录 traverse 函数递归时的路径
self.path = []
# 记录所有从根节点到叶子节点的路径
self.res = []
def traverse(self, root: TreeNode):
if root is None:
return
# root 是叶子节点
if root.left is None and root.right is None:
self.path.append(str(root.val))
# 将这条路径装入 res
self.res.append("->".join(self.path))
self.path.pop()
return
# 前序遍历位置
self.path.append(str(root.val))
# 递归遍历左右子树
self.traverse(root.left)
self.traverse(root.right)
# 后序遍历位置
self.path.pop()
129. 求根节点到叶节点数字之和 | 力扣 | LeetCode |
给你一个二叉树的根节点 root
,树中每个节点都存放有一个 0
到 9
之间的数字。
每条从根节点到叶节点的路径都代表一个数字:
- 例如,从根节点到叶节点的路径
1 -> 2 -> 3
表示数字123
。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1:
输入:root = [1,2,3] 输出:25 解释: 从根到叶子节点路径1->2
代表数字12
从根到叶子节点路径1->3
代表数字13
因此,数字总和 = 12 + 13 =25
示例 2:
输入:root = [4,9,0,5,1] 输出:1026 解释: 从根到叶子节点路径4->9->5
代表数字 495 从根到叶子节点路径4->9->1
代表数字 491 从根到叶子节点路径4->0
代表数字 40 因此,数字总和 = 495 + 491 + 40 =1026
提示:
- 树中节点的数目在范围
[1, 1000]
内 0 <= Node.val <= 9
- 树的深度不超过
10
class Solution:
def __init__(self):
self.path = ""
self.res = 0
def sumNumbers(self, root: TreeNode) -> int:
# 遍历一遍二叉树就能出结果
self.traverse(root)
return self.res
# 二叉树遍历函数
def traverse(self, root):
if root is None:
return
# 前序遍历位置,记录节点值
self.path += str(root.val)
if root.left is None and root.right is None:
# 到达叶子节点,累加路径和
self.res += int(self.path)
# 二叉树递归框架,遍历左右子树
self.traverse(root.left)
self.traverse(root.right)
# 后续遍历位置,撤销节点值
self.path = self.path[:-1]
199. 二叉树的右视图 | 力扣 | LeetCode |
给定一个二叉树的 根节点 root
,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
示例 2:
输入: [1,null,3] 输出: [1,3]
示例 3:
输入: [] 输出: []
提示:
- 二叉树的节点个数的范围是
[0,100]
-100 <= Node.val <= 100
from collections import deque
class Solution:
# BFS 层序遍历解法
def rightSideView(self, root) -> list:
res = []
if root is None:
return res
# BFS 层序遍历,计算右侧视图
q = deque([root])
# while 循环控制从上向下一层层遍历
while q:
sz = len(q)
# 每一层头部就是最右侧的元素
last = q[0]
for i in range(sz):
cur = q.popleft()
# 控制每一层从右向左遍历
if cur.right:
q.append(cur.right)
if cur.left:
q.append(cur.left)
# 每一层的最后一个节点就是二叉树的右侧视图
res.append(last.val)
return res
# DFS 递归遍历解法
def rightSideView_DFS(self, root) -> list:
self.res = []
# 记录递归的层数
self.depth = 0
self.traverse(root)
return self.res
# 二叉树遍历函数
def traverse(self, root):
if root is None:
return
# 前序遍历位置
self.depth += 1
if len(self.res) < self.depth:
# 这一层还没有记录值
# 说明 root 就是右侧视图的第一个节点
self.res.append(root.val)
# 注意,这里反过来,先遍历右子树再遍历左子树
# 这样首先遍历的一定是右侧节点
self.traverse(root.right)
self.traverse(root.left)
# 后序遍历位置
self.depth -= 1
298. 二叉树最长连续序列 | 力扣 | LeetCode |
给你一棵指定的二叉树的根节点 root
,请你计算其中 最长连续序列路径 的长度。
最长连续序列路径 是依次递增 1 的路径。该路径,可以是从某个初始节点到树中任意节点,通过「父 - 子」关系连接而产生的任意路径。且必须从父节点到子节点,反过来是不可以的。
示例 1:
输入:root = [1,null,3,2,4,null,null,null,5] 输出:3 解释:当中,最长连续序列是3-4-5 ,所以
返回结果为3 。
示例 2:
输入:root = [2,null,3,2,null,1] 输出:2 解释:当中,最长连续序列是2-3 。注意,不是
3-2-1,所以
返回2 。
提示:
- 树中节点的数目在范围
[1, 3 * 104]
内 -3 * 104 <= Node.val <= 3 * 104
class Solution:
def __init__(self):
self.maxLen = 0
def longestConsecutive(self, root: TreeNode) -> int:
self.traverse(root, 1, float('-inf'))
return self.maxLen
# 遍历二叉树,根据父节点的值判断连续的序列长度
def traverse(self, root: TreeNode, len: int, parentVal: int):
if root is None:
return
if parentVal + 1 == root.val:
len += 1
else:
len = 1
# 更新最长连续序列的长度
self.maxLen = max(self.maxLen, len)
# 遍历框架
self.traverse(root.left, len, root.val)
self.traverse(root.right, len, root.val)
988. 从叶结点开始的最小字符串 | 力扣 | LeetCode |
给定一颗根结点为 root
的二叉树,树中的每一个结点都有一个 [0, 25]
范围内的值,分别代表字母 'a'
到 'z'
。
返回 按字典序最小 的字符串,该字符串从这棵树的一个叶结点开始,到根结点结束。
注:字符串中任何较短的前缀在 字典序上 都是 较小 的:
- 例如,在字典序上
"ab"
比"aba"
要小。叶结点是指没有子结点的结点。
节点的叶节点是没有子节点的节点。
示例 1:
输入:root = [0,1,2,3,4,3,4] 输出:"dba"
示例 2:
输入:root = [25,1,3,1,3,0,2] 输出:"adz"
示例 3:
输入:root = [2,2,1,null,1,0,null,0] 输出:"abc"
提示:
- 给定树的结点数在
[1, 8500]
范围内 0 <= Node.val <= 25
前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式,这道题需要用到「遍历」的思维。
代码看起来虽然多,但思路非常简单:用 path
维护递归遍历的路径,到达叶子节点的时候判断字典序最小的路径。
不要忘了在叶子节点的时候也要正确维护 path
变量,而且要把 StringBuilder 中的字符串反转才是题目想要的答案。
class Solution:
def smallestFromLeaf(self, root: TreeNode) -> str:
self.traverse(root)
return self.res
# 遍历过程中的路径
path = ""
res = None
# 二叉树遍历函数
def traverse(self, root):
if root is None:
return
if root.left is None and root.right is None:
# 找到叶子结点,比较字典序最小的路径
# 结果字符串是从叶子向根,所以需要反转
self.path = chr(ord('a') + root.val) + self.path
s = self.path
if self.res is None or self.res > s:
# 如果字典序更小,则更新 res
self.res = s
# 恢复,正确维护 path 中的元素
self.path = self.path[1:]
return
# 前序位置
self.path = chr(ord('a') + root.val) + self.path
self.traverse(root.left)
self.traverse(root.right)
# 后序位置
self.path = self.path[1:]
1022. 从根到叶的二进制数之和 | 力扣 | LeetCode |
前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式,这道题需要用到「遍历」的思维。
用 path
变量维护每一条从根节点到叶子节点的路径形成的二进制数,到了叶子节点之后将这条路径的二进制数累加到 res
中即可。
class Solution:
def sumRootToLeaf(self, root: TreeNode) -> int:
self.path = 0
self.res = 0
self.traverse(root)
return self.res
def traverse(self, root: TreeNode):
if root is None:
return
if root.left is None and root.right is None:
# 叶子节点
self.res += self.path << 1 | root.val
return
# 前序位置
self.path = self.path << 1 | root.val
self.traverse(root.left)
self.traverse(root.right)
# 后序位置
self.path = self.path >> 1
1457. 二叉树中的伪回文路径 | 力扣 | LeetCode |
前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式,这道题需要用到「遍历」的思维。
遍历一遍二叉树就能得到每条路径上的数字,但这题的考点在于,如何判断一组数字是否存在一个回文串组合?
稍加思考不难想到:如果一组数字中,只有最多一个数字出现的次数为奇数,剩余数字的出现次数均为偶数,那么这组数字可以组成一个回文串。
题目说了 1 <= root.val <= 9
,所以我们可以用一个大小为 10 的 count
数组做计数器来记录每条路径上的元素出现次数,到达叶子节点之后根据元素出现的次数判断是否可以构成回文串。
当然,我们也可以用更巧妙的位运算来实现上述逻辑:
1、首先用到异或运算的特性,1 ^ 1 = 0, 0 ^ 0 = 0, 1 ^ 0 = 1。
2、其次用到 n & (n - 1)
去除二进制最后一个 1 的技巧,详见 东哥教你几招常用的位运算技巧。
我同时实现了这两种方法,供你参考。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.count = [0] * 10
self.res = 0
def pseudoPalindromicPaths(self, root: TreeNode) -> int:
self.traverse(root)
return self.res
# 二叉树遍历函数
def traverse(self, root: TreeNode):
if root is None:
return
if root.left is None and root.right is None:
# 遇到叶子节点,判断路径是否是伪回文串
self.count[root.val] += 1
# 如果路径上出现奇数次的数字个数大于 1,
# 则不可能组成回文串,反之则可以组成回文串
odd = 0
for n in self.count:
if n % 2 == 1:
odd += 1
if odd <= 1:
self.res += 1
self.count[root.val] -= 1
return
self.count[root.val] += 1
# 二叉树遍历框架
self.traverse(root.left)
self.traverse(root.right)
self.count[root.val] -= 1
# 用位运算代替数组计数,进一步提升效率
class Solution2:
def __init__(self):
self.count = 0
self.res = 0
def pseudoPalindromicPaths(self, root: TreeNode) -> int:
self.traverse(root)
return self.res
# 二叉树遍历函数
def traverse(self, root: TreeNode):
if root is None:
return
if root.left is None and root.right is None:
# 遇到叶子节点,判断路径是否是伪回文串
self.count ^= (1 << root.val)
# 判断二进制中只有一位 1,原理见 https://labuladong.online/algo/frequency-interview/bitwise-operation/
if (self.count & (self.count - 1)) == 0:
self.res += 1
self.count ^= (1 << root.val)
return
self.count ^= (1 << root.val)
# 二叉树遍历框架
self.traverse(root.left)
self.traverse(root.right)
self.count ^= (1 << root.val)
1740. 找到二叉树中的距离 | 力扣 | LeetCode |
给定一棵二叉树的根节点 root
以及两个整数 p
和 q
,返回该二叉树中值为 p
的结点与值为 q
的结点间的 距离 。
两个结点间的 距离 就是从一个结点到另一个结点的路径上边的数目。
示例 1:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 0 输出:3 解释:在 5 和 0 之间有 3 条边:5-3-1-0
示例 2:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 7 输出:2 解释:在 5 和 7 之间有 2 条边:5-2-7
示例 3:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 5 输出:0 解释:一个结点与它本身之间的距离为 0
提示:
- 树中结点个数的范围在
[1, 104]
. 0 <= Node.val <= 109
- 树中所有结点的值都是唯一的.
p
和q
是树中结点的值.
这道题很明显是最近公共祖先问题(LCA)的拓展,原版的 LCA 问题是让我们返回最近公共祖先节点,现在相当于是在问 p
和 q
到最近公共祖先的树枝的距离之和。
不过说实话,这题的难度还是比较大的,需要你认真阅读我写的 一文秒杀所有二叉树最近公共祖先问题,理解 LCA 问题解法逐步演进的原理,然后再来看这道题。
具体看代码注释吧,最好结合 二叉树心法(纲领篇) 体悟一下二叉树的遍历顺序,毕竟递归算法不是线性执行的,只要搞明白代码的执行顺序就可以更深刻地理解递归。
class Solution:
def findDistance(self, root: TreeNode, p: int, q: int) -> int:
self.lca(root, p, q)
return self.res
found = False
res = 0
# 定义:当子树中不包含 p 或 q 时,返回 0;
# 当子树中仅包含 p 或 q 中的一个时,返回 root 到 p 或 q 的距离;
# 当子树中同时包含 p 和 q 时,返回一个无意义的值(答案会被存在外部变量 res 中)
def lca(self, root: TreeNode, p: int, q: int) -> int:
if self.found:
# found 为 true 时答案已经被记录在全局 res 中
# 递归函数的返回值已不需要了,此时返回什么值都无所谓
return 123
if root is None:
return 0
left = self.lca(root.left, p, q)
right = self.lca(root.right, p, q)
if left == 0 and right == 0:
# root 的左右子树都不包含 p 或 q
if root.val == p or root.val == q:
return 1
return 0
if left != 0 and right != 0 and not self.found:
# 当前节点 root 就是 p, q 的最近公共祖先节点
# 答案已经算出来了,更新全局变量
self.res = left + right
# 这个递归函数的返回值已经不重要了,让它终止递归
self.found = True
return 456
# 此时 left 和 right 有一个为 0,即只找到了一个节点
# branch 就是到该节点的距离
branch = right if left == 0 else left
if root.val == p or root.val == q:
self.res = branch
return branch + 1
1257. 最小公共区域 | 力扣 | LeetCode |
给你一些区域列表 regions
,每个列表的第一个区域都包含这个列表内所有其他区域。
很自然地,如果区域 X
包含区域 Y
,那么区域 X
比区域 Y
大。
给定两个区域 region1
和 region2
,找到同时包含这两个区域的 最小 区域。
如果区域列表中 r1
包含 r2
和 r3
,那么数据保证 r2
不会包含 r3
。
数据同样保证最小公共区域一定存在。
示例 1:
输入: regions = [["Earth","North America","South America"], ["North America","United States","Canada"], ["United States","New York","Boston"], ["Canada","Ontario","Quebec"], ["South America","Brazil"]], region1 = "Quebec", region2 = "New York" 输出:"North America"
提示:
2 <= regions.length <= 10^4
region1 != region2
- 所有字符串只包含英文字母和空格,且最多只有 20 个字母。
这道题有意思,很显然是一个多叉树最近公共祖先的问题。建议看下这篇文章 二叉树最近公共祖先 中讲到的 1650. 二叉树的最近公共祖先 III。
我们可以用题目输入的 regions
结合哈希表构建多叉树,且节点指向关系是从子节点指向父节点,方便我们根据 region1, region2
回溯最近的公共祖先。构建出来之后可以直接套用 1650 的解题思路,利用 单链表的双指针技巧汇总 中讲的寻找单链表交点的算法找到答案。
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译。
# 本代码的正确性已通过力扣验证,但可能缺失注释。必要时请对照我的 java 代码查看。
class Solution:
def __init__(self):
self.tree = {}
def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
# 构建反向链接的多叉树,key 为子节点,value 为父节点
for list in regions:
parent = list[0]
for child in list[1:]:
self.tree[child] = parent
# 转化为 1650. 二叉树的最近公共祖先 III 的解法
return self.lowestCommonAncestor(region1, region2)
def lowestCommonAncestor(self, p: str, q: str) -> str:
# 施展链表双指针技巧
a, b = p, q
while a != b:
# a 走一步,如果走到根节点,转到 q 节点
a = self.tree.get(a, q)
# b 走一步,如果走到根节点,转到 p 节点
b = self.tree.get(b, p)
return a