发表更新数据结构与算法 / LeetCode75学习计划16 分钟读完 (大约2377个字)

LeetCode75学习计划-树的DFS/BFS

算法解题思路很多会借鉴于题解区，如果侵权请联系删除。

本章节知识点为树的DFS/BFS。

二叉树的最大深度

题目标签：

  • 树
  • 深度优先搜索
  • 广度优先搜索

题目难度： Easy

题目描述：

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

解题思路：

  • 递归肯定是最简单易懂的实现方式，也就是采用深度优先的思路
  • 每一个节点的深度 = 1 + max(左子树的最大深度， 右子树的最大深度)

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type TreeNode struct {
  Val int
  Left *TreeNode
  Right *TreeNode
}
func maxDepth(root *TreeNode) int {
  // 如果节点不存在则深度为0
  if root == nil {
    return 0
  }
  // 1 + max(左子树的最大深度, 右子树的最大深度)
  return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

叶子相似的树

题目标签：

  • 树
  • 深度优先搜索
  • 二叉搜索树

题目难度： Easy

题目描述：

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

解题思路：

  • 我们可以采用深度优先搜索，在搜索的时候总是先搜索左子节点，再搜索右子节点，这样就能得到一棵树的叶值序列
  • 以此方式得到两棵树的叶值序列比对即可

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func leafSimilar(root1, root2 *TreeNode) bool {
  vals := []int{}
  // 深度优先算法
  var dfs func(*TreeNode)
  dfs = func(node *TreeNode) {
    if node == nil {
      return
    }
    // 如果左右节点都没有，那么这个就是叶子节点，记录这个值
    if node.Left == nil && node.Right == nil {
      vals = append(vals, node.Val)
      return
    }
    // 先递归左子树，再递归右子树
    dfs(node.Left)
    dfs(node.Right)
  }
  // 先计算root1的叶值序列
  dfs(root1)
  vals1 := append([]int(nil), vals...)
  // 重置vals的值
  vals = []int{}
  // 计算root2的叶值序列
  dfs(root2)
  // 长度不一致则叶值序列一定不一致
  if len(vals) != len(vals1) {
    return false
  }
  // 比对两个叶值序列
  for i,v := range vals1 {
    if v != vals[i] {
      return false
    }
  }
  return true
}

统计二叉树中的好节点

题目标签：

  • 树
  • 深度优先搜索
  • 广度优先搜索

题目难度： Medium

题目描述：

给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。

「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值

解题思路：

  • 采用深度优先的方式，统计好节点的数量。在深度优先过程中，记录根节点到当前节点到最大值（不包括当前节点），如果当前节点大于那个最大值，那么这个节点就是好节点

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func goodNodes(root *TreeNode) int {
  // 好节点的数量
  goodNum := 0
  // dfs算法
  var dfs func(*TreeNode, int)
  dfs = func(node *TreeNode, max int) {
    if node == nil {
      return
    }
    // 如果当前节点大于路径上的最大值，则为好节点，并更新最大值后递归子节点
    if node.Val >= max {
      goodNum ++
      max = node.Val
    }
    dfs(node.Left, max)
    dfs(node.Right, max)
  }

  if root == nil {
    return goodNum
  }
  dfs(root, root.Val)
  return goodNum
}

路径总和 III

题目标签：

  • 树
  • 深度优先搜索

题目难度： Medium

题目描述：

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

解题思路：

  • 穷举，计算每一个节点开始向下查找的路径有多少种

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func pathSum(root *TreeNode, targetSum int) int {
  if root == nil {
    return 0
  }
  // 通过递归调用的方式，计算以每一个节点作为开始的路径有多少种然后累加
  res := 0
  // 以自身为开始节点
  res += rootSum(root, targetSum)
  // 递归调用,以左右子节点作为开始节点
  res += pathSum(root.Left, targetSum)
  res += pathSum(root.Right, targetSum)
  return res
}
func rootSum(root *TreeNode, targetSum int) int {
  res := 0
  if root == nil {
    return res 
  }
  if root.Val == targetSum {
    res ++
  }
  res += rootSum(root.Left, targetSum - root.Val)
  res += rootSum(root.Right, targetSum - root.Val)
  return res
}

二叉树中的最长交错路径

题目标签：

  • 树
  • 深度优先搜索

题目难度： Medium

题目描述：

给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：

  • 选择二叉树中 任意 节点和一个方向（左或者右）。
  • 如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
  • 改变前进方向：左变右或者右变左。
  • 重复第二步和第三步，直到你在树中无法继续移动。

交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。

请你返回给定树中最长 交错路径 的长度。

解题思路：

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func longestZigZag(root *TreeNode) int {
  res := 0
  var dfs func(*TreeNode, int, int)
  dfs = func(node *TreeNode, direction int, length int) {
    if node == nil {
      return
    }
    res = max(res, length)
    if direction == 0 {
      dfs(node.Left, 1, length + 1)
      dfs(node.Right, 0, 1)
    } else {
      dfs(node.Right, 0, length + 1)
      dfs(node.Left, 1, 1)
    }
  }
  dfs(root, 0, 0)
  dfs(root, 1, 0)
  return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

二叉树的最近公共祖先

题目标签：

  • 树
  • 深度优先搜索

题目难度： Medium

题目描述：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

解题思路：

  • 递归调用，分别查找两侧的子树

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  if root == nil {
    return nil
  }
  // 如果root.Val 等于 p.Val 或者 q.Val那么root就是公共祖先
  if root.Val == p.Val || root.Val == q.Val {
    return root
  }
  // 递归调用子树，如果p和q分别在左右子树上，那么left和right都会返回其对应的树节点
  // 如果p和q在同一侧的子树上，那么层级更浅的会作为树节点返回，另一侧的子树会返回nil
  left := lowestCommonAncestor(root.Left, p, q)
  right := lowestCommonAncestor(root.Right, p, q)
  // 分别在两侧的子树上，那么root就是公共祖先
  if left != nil && right != nil {
    return root
  }
  // 在同一侧的子树上，则返回其树节点
  if left == nil {
    return right
  }
  return left
}

二叉树的右视图

题目标签：

  • 树
  • 广度优先搜索

题目难度： Medium

题目描述：

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解题思路：

  • 对于树的每一层，最右侧的一个节点就是我们能看到的节点，所以可以使用广度优先的算法

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func rightSideView(root *TreeNode) []int {
  res := []int{}
  if root == nil {
    return res
  }

  queue := []*TreeNode{root}
  for len(queue) > 0 {
    // 最后一个节点的值就是最右侧的一个
    res = append(res, queue[len(queue) - 1].Val)
    // 复制一份queue，然后将queue清空
    // 循环复制的queue的内容，将其子节点从左到右加入到queue中，这样queue中的最后一个节点是下一层的最右侧节点，直到最后一层
    help := queue
    queue = nil
    for _, v := range help {
      if v.Left != nil {
        queue = append(queue, v.Left)
      }
      if v.Right != nil {
        queue = append(queue, v.Right)
      }
    }
  }
  return res
}

最大层内元素和

题目标签：

  • 树
  • 广度优先搜索

题目难度： Medium

题目描述：

给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。

请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。

解题思路：

  • 与上一题的解题思路类似， 还是广度优先遍历，计算每一层的元素和即可
  • 依然采用一个队列，不断的入队、出队，计算完每一层
  • 我们在统计一层节点的元素和的时候，可以将下一层的内容加入到队列中

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func maxLevelSum(root *TreeNode) int {
  // 初始化结果和最大和
  res := 1
  maxSum := root.Val
  // 采用一个队列, 不断的入队出队，计算每一层的和
  queue := []*TreeNode{root}
  for level := 1; len(queue) > 0; level ++ {
    // 当前队列中是同一层的内容，先出队进行求和
    temp := queue
    queue = nil
    sum := 0
    for _, node := range temp {
      // 累加当前层的和
      sum += node.Val
      // 将下一层的节点加入到队列中
      if node.Left != nil {
        queue = append(queue, node.Left)
      } 
      if node.Right != nil {
        queue = append(queue, node.Right)
      }
    }
    // 如果当前层的和大于之前计算的最大和，则当前层作为结果
    if sum > maxSum {
      maxSum = sum
      res = level
    }
  }
  return res
}

LeetCode75学习计划-树的DFS/BFS

https://zhaolei-hu.github.io/2023/10/10/LeetCode75学习计划-树的DFS-BFS/

作者

胡兆磊

发布于

2023-10-10

更新于

2024-04-03

许可协议

#
关注我

分类

最新文章

归档

标签

BFS2
CSS5
DFS2
Dart1
Database1
Decorator1
EggJs3
EggJss1
ElementUI1
EventEmitter1
Flutter1
GetX1
Gin1
Go2
HarmonyOS1
IndexedDB1
JavaScript1
Javascript13
LeetCode12
Mongodb1
Mysql1
NestJs20
NodeJs28
Promise1
Proxy2
Python1
Reflect2
Sass3
Scss3
TypeScript1
Vue10
Vue-Router1
Web Storage1
axios7
canvas1
cli1
cron表达式1
hexo1
log4js1
lunarvim1
monorepo1
mustache1
neovim1
pinia1
typescript2
yarn1
二分查找1
二叉搜索树1
二叉树1
前缀和1
前缀树1
动态规划2
双指针1
哈希表1
哈希集合1
图1
字符串1
排序算法3
数组1
文件上传1
栈1
源码1
滑动窗口1
背包问题1
装饰器1
链表1
队列1
×