算法笔试-树
Updated Time
Category
Tags
关于语言：一刷用 Golang，二刷用 Rust
题单
遍历二叉树
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 144. 二叉树的前序遍历 | 简单 | ||
| 94. 二叉树的中序遍历 | 简单 | ||
| 145. 二叉树的后序遍历 | 简单 | ||
| 872. 叶子相似的树 | 第 94 场周赛 Q1 | 简单 | 1288 |
| 404. 左叶子之和 | 简单 | ||
| 671. 二叉树中第二小的节点 | 简单 |
自顶向下 DFS
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 104. 二叉树的最大深度 | 简单 | ||
| 111. 二叉树的最小深度 | 简单 | ||
| 112. 路径总和 | 简单 | ||
| 129. 求根节点到叶节点数字之和 | 中等 | ||
| 199. 二叉树的右视图 | 中等 | ||
| 1448. 统计二叉树中好节点的数目 | 第 26 场双周赛 Q3 | 中等 | 1360 |
| 1457. 二叉树中的伪回文路径 | 第 190 场周赛 Q3 | 中等 | 1405 |
| 1315. 祖父节点值为偶数的节点和 | 第 17 场双周赛 Q3 | 中等 | 1427 |
| 988. 从叶结点开始的最小字符串 | 第 122 场周赛 Q2 | 中等 | 1429 |
| 1026. 节点与其祖先之间的最大差值 | 第 132 场周赛 Q2 | 中等 | 1446 |
| 1022. 从根到叶的二进制数之和 | 第 131 场周赛 Q2 | 简单 | 1462 |
| 623. 在二叉树中增加一行 | 中等 | ||
| 1372. 二叉树中的最长交错路径 | 第 21 场双周赛 Q3 | 中等 | 1713 |
| 971. 翻转二叉树以匹配先序遍历 | 第 118 场双周赛 Q3 | 中等 | 1787 |
| 1443. 收集树上所有苹果的最少时间 | 第 188 场周赛 Q3 | 中等 | 1683 |
| 1377. T 秒后青蛙的位置 | 第 179 场周赛 Q4 | 困难 | 1824 |
| 993. 二叉树的堂兄弟节点 | 第 124 场周赛 Q1 | 简单 | 1288 |
自底向上 DFS
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 965. 单值二叉树 | 第 117 场周赛 Q1 | 简单 | 1178 |
| 100. 相同的树 | 简单 | ||
| 101. 对称二叉树 | 简单 | ||
| 951. 翻转等价二叉树 | 第 113 场周赛 Q2 | 中等 | 1477 |
| 110. 平衡二叉树 | 简单 | ||
| 226. 翻转二叉树 | 简单 | ||
| 617. 合并二叉树 | 简单 | ||
| 2331. 计算布尔二叉树的值 | 第 82 场双周赛 Q1 | 简单 | 1304 |
| 508. 出现次数最多的子树元素和 | 中等 | ||
| 563. 二叉树的坡度 | 简单 | ||
| 606. 根据二叉树创建字符串 | 中等 | ||
| 2265. 统计值等于子树平均值的节点数 | 第 292 场周赛 Q2 | 中等 | 1473 |
| 1339. 分裂二叉树的最大乘积 | 第 174 场周赛 Q3 | 中等 | 1675 |
| 1145. 二叉树着色游戏 | 第 148 场周赛 Q2 | 中等 | 1741 |
| 572. 另一棵树的子树 | 简单 | ||
| 1530. 好叶子节点对的数量 | 第 199 场周赛 Q3 | 中等 | 1746 |
| 814. 二叉树剪枝 | 第 79 场周赛 Q2 | 中等 | 1380 |
| 1325. 删除给定值的叶子节点 | 第 172 场周赛 Q3 | 中等 | 1407 |
| 1110. 删点成林 | 第 144 场周赛 Q3 | 中等 | 1511 |
| 1376. 通知所有员工所需的时间 | 第 179 场周赛 Q3 | 中等 | 1561 |
树的直径
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 543. 二叉树的直径 | 简单 | ||
| 687. 最长同值路径 | 中等 | ||
| 124. 二叉树中的最大路径和 | 困难 | ||
| 2385. 感染二叉树需要的总时间 | 第 307 场周赛 Q3 | 中等 | 1711 |
最近公共祖先（LCA）
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 236. 二叉树的最近公共祖先 | 中等 | ||
| 235. 二叉搜索树的最近公共祖先 | 中等 | ||
| 1123. 最深叶节点的最近公共祖先 | 第 145 场周赛 Q2 | 中等 | 1607 |
BFS
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 102. 二叉树的层序遍历 | 中等 | ||
| 103. 二叉树的锯齿形层序遍历 | 中等 | ||
| 107. 二叉树的层序遍历 II | 中等 | ||
| 513. 找树左下角的值 | 中等 | ||
| 515. 在每个树行中找最大值 | 中等 | ||
| 637. 二叉树的层平均值 | 简单 | ||
| 1161. 最大层内元素和 | 第 150 场周赛 Q2 | 中等 | 1250 |
| 2583. 二叉树中的第 K 大层和 | 第 335 场周赛 Q2 | 中等 | 1374 |
| 1302. 层数最深叶子节点的和 | 第 16 场双周赛 Q3 | 中等 | 1388 |
题解
144. 二叉树的前序遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) []int {
ans := make([]int, 0)
var dfs func(*TreeNode)
dfs = func (r *TreeNode) {
if r == nil {
return
}
ans = append(ans, r.Val)
dfs(r.Left)
dfs(r.Right)
}
dfs(root)
return ans
}
94. 二叉树的中序遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) (ans []int) {
var dfs func(*TreeNode)
dfs = func(r *TreeNode) {
if r == nil {
return
}
dfs(r.Left)
ans = append(ans, r.Val)
dfs(r.Right)
}
dfs(root)
return
}
145. 二叉树的后序遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func postorderTraversal(root *TreeNode) (ans []int) {
var dfs func(*TreeNode)
dfs = func(r *TreeNode) {
if r == nil {
return
}
dfs(r.Left)
dfs(r.Right)
ans = append(ans, r.Val)
}
dfs(root)
return
}
872. 叶子相似的树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
var dfs func(*TreeNode, *[]int)
dfs = func(r *TreeNode, path *[]int) {
if r == nil {
return
}
if r.Left == nil && r.Right == nil {
*path = append(*path, r.Val)
}
dfs(r.Left, path)
dfs(r.Right, path)
}
p1, p2 := make([]int, 0), make([]int, 0)
dfs(root1, &p1)
dfs(root2, &p2)
if len(p1) != len(p2) {
return false
}
for i := 0; i < len(p1); i++ {
if p1[i] != p2[i] {
return false
}
}
return true
}
404. 左叶子之和
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumOfLeftLeaves(root *TreeNode) int {
if root == nil {
return 0
}
ans := 0
if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
ans = root.Left.Val
}
return ans + sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}
671. 二叉树中第二小的节点
题目描述，「如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个」，因此对于二叉树中的任意节点 \(x\)，\(x\) 的值不大于以 \(x\) 为根的子树中所有节点的值。
令 \(x\) 为二叉树的根节点，可以得出结论：二叉树根节点的值即为所有节点中的最小值。
func findSecondMinimumValue(root *TreeNode) int {
ans := -1
rootVal := root.Val
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node == nil || ans != -1 && node.Val >= ans {
return
}
if node.Val > rootVal {
ans = node.Val
}
dfs(node.Left)
dfs(node.Right)
}
dfs(root)
return ans
}
104. 二叉树的最大深度
解法一：自顶向下，解法二：自底向上
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxDepth(root *TreeNode) (ans int) {
var dfs func(*TreeNode, int)
dfs = func(r *TreeNode, depth int) {
if r == nil {
return
}
ans = max(ans, depth)
dfs(r.Left, depth + 1)
dfs(r.Right, depth + 1)
}
dfs(root, 1)
return ans
}
func maxDepth(root *TreeNode) int {
var dfs func(*TreeNode) int
dfs = func(r *TreeNode) int {
if r == nil {
return 0
}
depth := max(dfs(r.Left), dfs(r.Right)) + 1
return depth
}
return dfs(root)
}
111. 二叉树的最小深度
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) int {
ans := math.MaxInt
var dfs func(*TreeNode, int)
dfs = func(r *TreeNode, p int) {
if r == nil {
return
}
if r.Left == nil && r.Right == nil {
ans = min(ans, p)
}
dfs(r.Left, p + 1)
dfs(r.Right, p + 1)
}
dfs(root, 1)
if ans == math.MaxInt {
return 0
}
return ans
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) int {
var dfs func(*TreeNode) int
dfs = func(root *TreeNode) int {
if root == nil {
return 0
}
l := dfs(root.Left)
r := dfs(root.Right)
if l > 0 && r > 0 {
return min(l, r) + 1
} else {
return l + r + 1
}
}
return dfs(root)
}
112. 路径总和
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func hasPathSum(root *TreeNode, targetSum int) bool {
var dfs func(*TreeNode, int) bool
dfs = func(r *TreeNode, s int) bool {
if r == nil {
return false
}
s += r.Val
if s == targetSum && r.Left == nil && r.Right == nil {
return true
}
return dfs(r.Left, s) || dfs(r.Right, s)
}
return dfs(root, 0)
}
129. 求根节点到叶节点数字之和
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumNumbers(root *TreeNode) (ans int) {
var dfs func(*TreeNode, int)
dfs = func(r *TreeNode, num int) {
if r == nil {
return
}
num = num * 10 + r.Val
if r.Left == nil && r.Right == nil {
ans += num
}
dfs(r.Left, num)
dfs(r.Right, num)
}
dfs(root, 0)
return
}
199. 二叉树的右视图
先递归右子树，再递归左子树，当某个深度首次到达时，对应的节点就在右视图中。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView(root *TreeNode) (ans []int) {
var dfs func(*TreeNode, int)
dfs = func(r *TreeNode, depth int) {
if r == nil {
return
}
if depth == len(ans) {
ans = append(ans, r.Val)
}
dfs(r.Right, depth + 1)
dfs(r.Left, depth + 1)
}
dfs(root, 0)
return
}
1457. 二叉树中的伪回文路径
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pseudoPalindromicPaths (root *TreeNode) (ans int) {
var dfs func(*TreeNode, int)
dfs = func(r *TreeNode, s int) {
if r == nil {
return
}
s ^= (1 << r.Val)
if r.Left == nil && r.Right == nil && bits.OnesCount(uint(s)) <= 1 {
ans++
}
dfs(r.Left, s)
dfs(r.Right, s)
}
dfs(root, 0)
return
}
1315. 祖父节点值为偶数的节点和
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumEvenGrandparent(root *TreeNode) (ans int) {
var dfs func(*TreeNode, int, int)
dfs = func(r *TreeNode, f, gf int) {
if r == nil {
return
}
if gf % 2 == 0 {
ans += r.Val
}
dfs(r.Left, r.Val, f)
dfs(r.Right, r.Val, f)
}
dfs(root, -1, -1)
return
}
988. 从叶结点开始的最小字符串
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func smallestFromLeaf(root *TreeNode) (ans string) {
var dfs func(*TreeNode, string)
dfs = func(r *TreeNode, path string) {
if r == nil {
return
}
path = string('a' + r.Val) + path
if r.Left == nil && r.Right == nil {
if ans == "" {
ans = path
} else {
ans = min(ans, path)
}
}
dfs(r.Left, path)
dfs(r.Right, path)
}
dfs(root, "")
return
}
1026. 节点与其祖先之间的最大差值
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxAncestorDiff(root *TreeNode) (ans int) {
ans = math.MinInt
var dfs func(*TreeNode, int, int)
dfs = func(r *TreeNode, mx, mn int) {
if r == nil {
return
}
ans = max(ans, mx - r.Val)
ans = max(ans, r.Val - mn)
dfs(r.Left, max(mx, r.Val), min(mn, r.Val))
dfs(r.Right, max(mx, r.Val), min(mn, r.Val))
}
dfs(root, root.Val, root.Val)
return
}
1022. 从根到叶的二进制数之和
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumRootToLeaf(root *TreeNode) (ans int) {
var dfs func(*TreeNode, int)
dfs = func(r *TreeNode, num int) {
if r == nil {
return
}
num = num << 1 | r.Val
if r.Left == r.Right {
ans += num
}
dfs(r.Left, num)
dfs(r.Right, num)
}
dfs(root, 0)
return
}
623. 在二叉树中增加一行
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func addOneRow(root *TreeNode, val int, depth int) *TreeNode {
var dfs func(*TreeNode, int)
dfs = func(r *TreeNode, p int) {
if r == nil {
return
}
if depth - 1 == p {
// 创建两个节点
newLeft := &TreeNode{val, r.Left, nil}
newRight := &TreeNode{val, nil, r.Right}
r.Left, r.Right = newLeft, newRight
} else {
dfs(r.Left, p + 1)
dfs(r.Right, p + 1)
}
}
if depth == 1 {
return &TreeNode{val, root, nil}
}
dfs(root, 1)
return root
}
1372. 二叉树中的最长交错路径
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func longestZigZag(root *TreeNode) (ans int) {
var dfs func(*TreeNode, int, int)
dfs = func(r *TreeNode, dir, cnt int) {
if r == nil {
return
}
ans = max(ans, cnt)
// 延续上一次的继续走
if dir == 0 {
dfs(r.Right, dir ^ 1, cnt + 1)
// 以当前节点为根节点
dfs(r.Left, 0, 1)
} else if dir == 1 {
dfs(r.Left, dir ^ 1, cnt + 1)
dfs(r.Right, 1, 1)
}
}
dfs(root.Left, 0, 1)
dfs(root.Right, 1, 1)
return
}
971. 翻转二叉树以匹配先序遍历
进行深度优先遍历，如果遍历到某一个节点的时候，节点值不能匹配，那么答案一定是
-1。
否则，当期望的下一个数字与即将遍历的子节点的值不同的时候，就需要翻转一下当前节点。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func flipMatchVoyage(root *TreeNode, voyage []int) []int {
ans := make([]int, 0)
idx := 0
var dfs func(*TreeNode) bool
dfs = func(r *TreeNode) bool {
if r == nil {
return true
}
if r.Val != voyage[idx] {
return false
}
idx += 1
if r.Left != nil && r.Left.Val != voyage[idx] {
ans = append(ans, r.Val)
return dfs(r.Right) && dfs(r.Left)
} else {
return dfs(r.Left) && dfs(r.Right)
}
}
if dfs(root) {
return ans
}
return []int{-1}
}
965. 单值二叉树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isUnivalTree(root *TreeNode) bool {
var dfs func(r, p *TreeNode) bool
dfs = func(r, p *TreeNode) bool {
if r == nil {
return true
}
if r.Val != p.Val {
return false
}
return dfs(r.Left, r) && dfs(r.Right, r)
}
return dfs(root, root)
}
100. 相同的树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil {
return false
} else if (p.Val != q.Val) {
return false
}
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
101. 对称二叉树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSymmetric(root *TreeNode) bool {
var dfs func(a, b *TreeNode) bool
dfs = func(a, b *TreeNode) bool {
if a == nil && b == nil {
return true
}
if a == nil || b == nil {
return false
}
return a.Val == b.Val && dfs(a.Left, b.Right) && dfs(a.Right, b.Left)
}
return dfs(root.Left, root.Right)
}
951. 翻转等价二叉树
如果二叉树 root1，和 root2
根节点值相等，那么只需要检查它们的孩子是不是相等就可以了。存在两种情况：
- 都为
null - 值相等孩子是否相等。由于可以翻转，所以需要判断两种情况。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {
if root1 == nil && root2 == nil {
return true
}
if root1 == nil || root2 == nil {
return false
}
if root1.Val != root2.Val {
return false
}
return (flipEquiv(root1.Left, root2.Left) && flipEquiv(root1.Right, root2.Right)) || (flipEquiv(root1.Left, root2.Right) && flipEquiv(root1.Right, root2.Left))
}
110. 平衡二叉树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isBalanced(root *TreeNode) bool {
var dfs func(*TreeNode) int
dfs = func(r *TreeNode) int {
if r == nil {
return 0
}
depthL := dfs(r.Left)
if depthL == -1 {
return -1
}
depthR := dfs(r.Right)
if depthR == -1 {
return -1
}
if abs(depthL - depthR) > 1 {
return -1
}
return max(depthL, depthR) + 1
}
return dfs(root) != -1
}
func abs(v int) int {
if v < 0 {
return -v
}
return v
}
226. 翻转二叉树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
var dfs func(c *TreeNode) *TreeNode
dfs = func(c *TreeNode) *TreeNode {
if c == nil {
return nil
}
l, r := dfs(c.Left), dfs(c.Right)
c.Left, c.Right = r, l
return c
}
return dfs(root)
}
617. 合并二叉树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
var dfs func(p, q *TreeNode) *TreeNode
dfs = func(p, q *TreeNode) *TreeNode {
if p == nil && q == nil {
return nil
} else if p == nil {
return q
} else if q == nil {
return p
} else {
p.Val += q.Val
}
p.Left = dfs(p.Left, q.Left)
p.Right = dfs(p.Right, q.Right)
return p
}
return dfs(root1, root2)
}
2331. 计算布尔二叉树的值
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func evaluateTree(root *TreeNode) bool {
var dfs func(c *TreeNode) bool
dfs = func(c *TreeNode) bool {
if c == nil {
return true
}
if c.Left == c.Right {
return c.Val == 1
}
l, r := dfs(c.Left), dfs(c.Right)
if c.Val == 2 {
return l || r
} else {
return l && r
}
}
return dfs(root)
}
508. 出现次数最多的子树元素和
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findFrequentTreeSum(root *TreeNode) []int {
var dfs func(r *TreeNode) int
cnt := make(map[int]int)
dfs = func(c *TreeNode) int {
if c == nil {
return 0
}
lSum, rSum := dfs(c.Left), dfs(c.Right)
cnt[lSum + rSum + c.Val]++
return lSum + rSum + c.Val
}
dfs(root)
mx := 0
for _, v := range cnt {
mx = max(mx, v)
}
ans := make([]int, 0)
for k, v := range cnt {
if v == mx {
ans = append(ans, k)
}
}
return ans
}
563. 二叉树的坡度
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findTilt(root *TreeNode) int {
ans := 0
var dfs func(c *TreeNode) int
dfs = func(c *TreeNode) int {
if c == nil {
return 0
}
l, r := dfs(c.Left), dfs(c.Right)
ans += abs(l - r)
return l + r + c.Val
}
dfs(root)
return ans
}
func abs(v int) int {
if v < 0 {
return -v
}
return v
}
606. 根据二叉树创建字符串
func tree2str(root *TreeNode) string {
switch {
case root == nil:
return ""
case root.Left == nil && root.Right == nil:
return strconv.Itoa(root.Val)
case root.Right == nil:
return fmt.Sprintf("%d(%s)", root.Val, tree2str(root.Left))
default:
return fmt.Sprintf("%d(%s)(%s)", root.Val, tree2str(root.Left), tree2str(root.Right))
}
}
2265. 统计值等于子树平均值的节点数
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func averageOfSubtree(root *TreeNode) (ans int) {
var dfs func(*TreeNode) (int, int)
dfs = func(c *TreeNode) (int, int) {
if c == nil {
return 0, 0
}
l, lCnt := dfs(c.Left)
r, rCnt := dfs(c.Right)
sum := l + r + c.Val
cnt := lCnt + rCnt + 1
if sum / cnt == c.Val {
ans++
}
return sum, cnt
}
dfs(root)
return
}
1339. 分裂二叉树的最大乘积
第一遍 dfs 求总和，第二遍枚举断哪条边
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxProduct(root *TreeNode) int {
mod := int64(1e9+7)
ans, total := int64(0), int64(0)
var dfs func(*TreeNode) int64
dfs = func(c *TreeNode) int64 {
if c == nil {
return 0
}
sum := int64(c.Val) + dfs(c.Left) + dfs(c.Right)
ans = max(ans, sum * (total - sum))
return sum
}
total = dfs(root)
dfs(root)
return int(ans % mod)
}
1145. 二叉树着色游戏
蓝色最优的点只有三个点可以选，就是红色点的三个相邻节点，所以只需要判断这三种情况即可。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func btreeGameWinningMove(root *TreeNode, n int, x int) bool {
var dfs func(*TreeNode) int
s1, s2 := 0, 0
dfs = func(c *TreeNode) int {
if c == nil {
return 0
}
l, r := dfs(c.Left), dfs(c.Right)
if c.Val == x {
s1, s2 = l, r
}
return l + r + 1
}
dfs(root)
return s1 > (n - s1) || s2 > (n - s2) || (n - s1 - s2 - 1) > (s1 + s2 + 1)
}
572. 另一棵树的子树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSame(s, t *TreeNode) bool {
if s == nil && t == nil {
return true
}
if s == nil || t == nil {
return false
}
if s.Val != t.Val {
return false
}
return isSame(s.Left, t.Left) && isSame(s.Right, t.Right)
}
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
if root == nil {
return false
}
if isSame(root, subRoot) {
return true
}
return isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}
1530. 好叶子节点对的数量
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func countPairs(root *TreeNode, distance int) (ans int) {
var dfs func(*TreeNode) []int
dfs = func(c *TreeNode) (ret []int) {
if c == nil {
return []int{}
}
if c.Left == c.Right {
return []int{1}
}
left := dfs(c.Left)
right := dfs(c.Right)
for _, l := range left {
ret = append(ret, l + 1)
}
for _, r := range right {
ret = append(ret, r + 1)
}
for _, l := range left {
for _, r := range right {
if l + r <= distance {
ans++
}
}
}
return
}
dfs(root)
return
}
814. 二叉树剪枝
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pruneTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
root.Left = pruneTree(root.Left)
root.Right = pruneTree(root.Right)
if root.Left == nil && root.Right == nil && root.Val == 0 {
return nil
}
return root
}
1325. 删除给定值的叶子节点
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func removeLeafNodes(root *TreeNode, target int) *TreeNode {
if root == nil {
return nil
}
root.Left = removeLeafNodes(root.Left, target)
root.Right = removeLeafNodes(root.Right, target)
if root.Left == root.Right && root.Val == target {
return nil
}
return root
}
1110. 删点成林
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func delNodes(root *TreeNode, to_delete []int) (ans []*TreeNode) {
del := make(map[int]bool)
for _, d := range to_delete {
del[d] = true
}
var dfs func(*TreeNode) *TreeNode
dfs = func(c *TreeNode) *TreeNode {
if c == nil {
return nil
}
// 如果 c 是要被删除的节点
// 那么其左右孩子一定成为根节点
c.Left = dfs(c.Left)
c.Right = dfs(c.Right)
if _, ok := del[c.Val]; !ok {
// 不删
return c
}
// 删
if c.Left != nil {
ans = append(ans, c.Left)
}
if c.Right != nil {
ans = append(ans, c.Right)
}
return nil
}
if dfs(root) != nil {
ans = append(ans, root)
}
return
}
543. 二叉树的直径
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func diameterOfBinaryTree(root *TreeNode) (ans int) {
var dfs func(*TreeNode) int
dfs = func(c *TreeNode) int {
if c == nil {
return -1
}
l, r := dfs(c.Left), dfs(c.Right)
ans = max(ans, l + r + 2)
return max(l, r) + 1
}
dfs(root)
return
}
687. 最长同值路径
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func longestUnivaluePath(root *TreeNode) (ans int) {
var dfs func(*TreeNode) int
dfs = func(c *TreeNode) int {
if c == nil {
return -1
}
l, r := dfs(c.Left), dfs(c.Right)
if c.Left != nil && c.Val != c.Left.Val {
l = -1
}
if c.Right != nil && c.Val != c.Right.Val {
r = -1
}
ans = max(ans, l + r + 2)
return max(l, r) + 1
}
dfs(root)
return
}
124. 二叉树中的最大路径和
题目求的是链，因此不必从叶子节点出发，所以需要加上一个 \(max\) 判断。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxPathSum(root *TreeNode) int {
ans := math.MinInt
var dfs func(*TreeNode) int
dfs = func(c *TreeNode) int {
if c == nil {
return 0
}
l, r := max(0, dfs(c.Left)), max(0, dfs(c.Right))
ans = max(ans, l + r + c.Val)
return max(l, r) + c.Val
}
dfs(root)
return ans
}
2385. 感染二叉树需要的总时间
// 三种情况：
// 1. 最长路径在 start 节点的左子树
// 2. 最长路径在 start 节点的右子树
// 3. 最长路径经过 start 的父节点
// 归纳成两种：
// 1. start 为根节点的最长子树直径
// 2. start 为叶子节点的最长树直径
func amountOfTime(root *TreeNode, start int) (ans int) {
var dfs func(*TreeNode) (int, bool)
dfs = func(c *TreeNode) (int, bool) {
if c == nil {
return 0, false
}
l, isL := dfs(c.Left)
r, isR := dfs(c.Right)
if c.Val == start {
// 当前节点是 start，计算子树最长直径
ans = max(ans, l, r)
// 已经找到了 start，返回 1 表示把 start 的子树删除
return 1, true
}
if isL || isR {
ans = max(ans, l + r)
if isL {
return l + 1, true
}
return r + 1, true
}
return max(l, r) + 1, false
}
dfs(root)
return
}
236. 二叉树的最近公共祖先
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || root == p || root == q {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left == nil {
return right
}
if right == nil {
return left
}
return root
}
235. 二叉搜索树的最近公共祖先
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root.Val > p.Val && root.Val > q.Val {
return lowestCommonAncestor(root.Left, p, q)
}
if root.Val < p.Val && root.Val < q.Val {
return lowestCommonAncestor(root.Right, p, q)
}
return root
}
1123. 最深叶节点的最近公共祖先
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func depth(root *TreeNode) int {
if root == nil {
return 0
}
l, r := depth(root.Left), depth(root.Right)
return max(l, r) + 1
}
func lcaDeepestLeaves(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
l, r := depth(root.Left), depth(root.Right)
if l == r {
return root
} else if l > r {
return lcaDeepestLeaves(root.Left)
} else {
return lcaDeepestLeaves(root.Right)
}
}
102. 二叉树的层序遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) (ans [][]int) {
if root == nil {
return [][]int{}
}
q := make([]*TreeNode, 0)
q = append(q, root)
for len(q) > 0 {
list := make([]int, 0)
for t := len(q); t > 0; t-- {
cur := q[0]
q = q[1:]
list = append(list, cur.Val)
if cur.Left != nil {
q = append(q, cur.Left)
}
if cur.Right != nil {
q = append(q, cur.Right)
}
}
ans = append(ans, list)
}
return
}
103. 二叉树的锯齿形层序遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func zigzagLevelOrder(root *TreeNode) (ans [][]int) {
if root == nil {
return
}
q := make([]*TreeNode, 0)
q = append(q, root)
for len(q) > 0 {
nxt := []*TreeNode{}
vals := make([]int, len(q))
for i, node := range q {
if len(ans) % 2 > 0 {
vals[len(q)-1-i] = node.Val
} else {
vals[i] = node.Val
}
if node.Left != nil {
nxt = append(nxt, node.Left)
}
if node.Right != nil {
nxt = append(nxt, node.Right)
}
}
q = nxt
ans = append(ans, vals)
}
return
}
513. 找树左下角的值
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findBottomLeftValue(root *TreeNode) (ans int) {
cur := []*TreeNode{root}
for len(cur) > 0 {
nxt := []*TreeNode{}
for i, node := range cur {
if i == 0 {
ans = node.Val
}
if node.Left != nil {
nxt = append(nxt, node.Left)
}
if node.Right != nil {
nxt = append(nxt, node.Right)
}
}
cur = nxt
}
return
}
515. 在每个树行中找最大值
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func largestValues(root *TreeNode) (ans []int) {
if root == nil {
return
}
cur := []*TreeNode{root}
for len(cur) > 0 {
nxt := []*TreeNode{}
mx := math.MinInt
for _, node := range cur {
mx = max(mx, node.Val)
if node.Left != nil {
nxt = append(nxt, node.Left)
}
if node.Right != nil {
nxt = append(nxt, node.Right)
}
}
cur = nxt
ans = append(ans, mx)
}
return
}
1376. 通知所有员工所需的时间
自顶向上，自底向下都能做
func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
g := make([][]int, n)
for u, v := range manager {
if v != -1 {
g[v] = append(g[v], u)
}
}
var dfs func(int) int
dfs = func(i int) int {
ret := 0
for _, v := range g[i] {
ret = max(ret, dfs(v))
}
return ret + informTime[i]
}
return dfs(headID)
}
1443. 收集树上所有苹果的最少时间
func minTime(n int, edges [][]int, hasApple []bool) int {
g := make([][]int, n)
for _, edge := range edges {
u, v := edge[0], edge[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
var dfs func(int, int) int
dfs = func(u, fa int) int {
ret := 0
for _, v := range g[u] {
if v == fa {
continue
}
ret += dfs(v, u)
}
if u != 0 && (hasApple[u] || ret > 0) {
ret += 2
}
return ret
}
return dfs(0, -1)
}
1377. T 秒后青蛙的位置
根据题意，青蛙只能一路向下。如果当前节点有 \(c\) 个子节点，那么跳到其中一个的概率是 \(\frac{1}{c}\)。因此答案可以看做是由若干分子为 \(1\) 的分数相乘得到，那么我们可以只计算分母，最后计算倒数。如果青蛙跳到了叶子节点，那么它会停留在叶子节点上。
func frogPosition(n int, edges [][]int, t int, target int) float64 {
g := make([][]int, n + 1)
g[1] = []int{0}
for _, edge := range edges {
u, v := edge[0], edge[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
ans := float64(0)
var dfs func(int, int, int, int) bool
dfs = func(i, fa, prod, time int) bool {
if i == target && (time == 0 || len(g[i]) == 1) {
ans = 1 / float64(prod)
return true
}
if i == target || time == 0 {
return false
}
for _, j := range g[i] {
if j == fa {
continue
}
if dfs(j, i, prod*(len(g[i]) - 1), time - 1) {
return true
}
}
return false
}
dfs(1, 0, 1, t)
return ans
}
1161. 最大层内元素和
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxLevelSum(root *TreeNode) (ans int) {
cur := []*TreeNode{root}
ans = 1
mx, level := root.Val, 1
for len(cur) > 0 {
nxt := []*TreeNode{}
sum := 0
for _, node := range cur {
sum += node.Val
if node.Left != nil {
nxt = append(nxt, node.Left)
}
if node.Right != nil {
nxt = append(nxt, node.Right)
}
}
if sum > mx {
mx = sum
ans = level
}
level++
cur = nxt
}
return
}
993. 二叉树的堂兄弟节点
dfs 记录当前节点，当前节点的父节点，当前节点的深度。如果之前找到了就做对比，没找到就记录。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isCousins(root *TreeNode, x int, y int) bool {
depth := 0
var father *TreeNode
var dfs func(*TreeNode, *TreeNode, int) bool
dfs = func(cur, fa *TreeNode, d int) bool {
if cur == nil {
return false
}
if cur.Val == x || cur.Val == y {
if depth > 0 {
return depth == d && fa != father
}
// 之前没找到
depth, father = d, fa
}
return dfs(cur.Left, cur, d + 1) || dfs(cur.Right, cur, d + 1)
}
return dfs(root, nil, 1)
}
2583. 二叉树中的第 K 大层和
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthLargestLevelSum(root *TreeNode, k int) int64 {
cur := []*TreeNode{root}
s := []int64{}
for len(cur) > 0 {
nxt := []*TreeNode{}
sum := int64(0)
for _, node := range cur {
sum += int64(node.Val)
if node.Left != nil {
nxt = append(nxt, node.Left)
}
if node.Right != nil {
nxt = append(nxt, node.Right)
}
}
cur = nxt
s = append(s, sum)
}
if len(s) < k {
return -1
}
slices.Sort(s)
return s[len(s)-k]
}
1302. 层数最深叶子节点的和
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func deepestLeavesSum(root *TreeNode) (ans int) {
cur := []*TreeNode{root}
for len(cur) > 0 {
nxt := []*TreeNode{}
sum := 0
for _, node := range cur {
sum += node.Val
if node.Left != nil {
nxt = append(nxt, node.Left)
}
if node.Right != nil {
nxt = append(nxt, node.Right)
}
}
cur = nxt
ans = sum
}
return
}
- 1. 题单
- 2. 题解
- 2.1. 144. 二叉树的前序遍历
- 2.2. 94. 二叉树的中序遍历
- 2.3. 145. 二叉树的后序遍历
- 2.4. 872. 叶子相似的树
- 2.5. 404. 左叶子之和
- 2.6. 671. 二叉树中第二小的节点
- 2.7. 104. 二叉树的最大深度
- 2.8. 111. 二叉树的最小深度
- 2.9. 112. 路径总和
- 2.10. 129. 求根节点到叶节点数字之和
- 2.11. 199. 二叉树的右视图
- 2.12. 1457. 二叉树中的伪回文路径
- 2.13. 1315. 祖父节点值为偶数的节点和
- 2.14. 988. 从叶结点开始的最小字符串
- 2.15. 1026. 节点与其祖先之间的最大差值
- 2.16. 1022. 从根到叶的二进制数之和
- 2.17. 623. 在二叉树中增加一行
- 2.18. 1372. 二叉树中的最长交错路径
- 2.19. 971. 翻转二叉树以匹配先序遍历
- 2.20. 965. 单值二叉树
- 2.21. 100. 相同的树
- 2.22. 101. 对称二叉树
- 2.23. 951. 翻转等价二叉树
- 2.24. 110. 平衡二叉树
- 2.25. 226. 翻转二叉树
- 2.26. 617. 合并二叉树
- 2.27. 2331. 计算布尔二叉树的值
- 2.28. 508. 出现次数最多的子树元素和
- 2.29. 563. 二叉树的坡度
- 2.30. 606. 根据二叉树创建字符串
- 2.31. 2265. 统计值等于子树平均值的节点数
- 2.32. 1339. 分裂二叉树的最大乘积
- 2.33. 1145. 二叉树着色游戏
- 2.34. 572. 另一棵树的子树
- 2.35. 1530. 好叶子节点对的数量
- 2.36. 814. 二叉树剪枝
- 2.37. 1325. 删除给定值的叶子节点
- 2.38. 1110. 删点成林
- 2.39. 543. 二叉树的直径
- 2.40. 687. 最长同值路径
- 2.41. 124. 二叉树中的最大路径和
- 2.42. 2385. 感染二叉树需要的总时间
- 2.43. 236. 二叉树的最近公共祖先
- 2.44. 235. 二叉搜索树的最近公共祖先
- 2.45. 1123. 最深叶节点的最近公共祖先
- 2.46. 102. 二叉树的层序遍历
- 2.47. 103. 二叉树的锯齿形层序遍历
- 2.48. 513. 找树左下角的值
- 2.49. 515. 在每个树行中找最大值
- 2.50. 1376. 通知所有员工所需的时间
- 2.51. 1443. 收集树上所有苹果的最少时间
- 2.52. 1377. T 秒后青蛙的位置
- 2.53. 1161. 最大层内元素和
- 2.54. 993. 二叉树的堂兄弟节点
- 2.55. 2583. 二叉树中的第 K 大层和
- 2.56. 1302. 层数最深叶子节点的和