图论算法（六）
自己对二叉树的了解：对二叉树的简单了解
可视化面板：算法可视化速查页
Online Compiler：Online Compiler, AI Tutor, and Visual Debugger for Python, Java, C, C++, and JavaScript
一、基础遍历
思考：
- 如何思考递归？（不要一来就看细节，将原问题划分成子问题）
- 为什么需要使用递归？
- 为什么递归是对的？（数学归纳法，当n=1时成立；假设n=m...）
- 计算机是怎么执行递归过程的？（通过压栈和出栈实现递归）
问：一直有个疑问，啥时候需要有返回值，啥时候不需要返回值？
- 看你怎么写递归，如果是自顶向下的话，可以没有返回值；如果是自底向上的话，就一定要有返回值。
思考结果：
- 我们在循环的时候，就是在重复的执行同样一份代码；我们将原问题划分成相同的子问题，在计划原问题和子问题的时候应该也使用同样一套代码
- 将原问题划分成更小的子问题，再把更小的子问题划分成在小的子问题，这个过程就是递归中的递，不断递下去，总会有尽头，就是递归的边界条件。
- 从递归的边界条件返回的时候，就是递归中的归。非边界条件。
- 在递归的时候，除了把节点传下去，还可以把路径上的节点个数也传下去。
- 递归怎么知道return到那个节点上呢？在递归的时候，计算机没有丢弃上一个节点，而是保存下来了，那用什么数据结构存储呢？用栈存储，递归的递就是压栈的过程，递归的归就是出栈的过程。
1.1、DFS基础
104. 二叉树的最大深度（20250326更新）
这道题从2020年开始就有提交，到现在2025年，终于有了不一样的理解。
我们需要知道什么是二叉树的最大深度，就是从跟节点到最下方叶子节点经过的节点个数为二叉树的最大深度。
所以我们只需要遍历一次，记录最大深度就可以了。DFS和BFS都可以。
// 自顶向下，维护一个入参，每次进入到节点，维护这个入参
class Solution {
int mx = 0;
public int maxDepth(TreeNode root) {
dfs(root, 0);
return mx;
}
void dfs(TreeNode root, int cnt){
// 非规范化
if(root == null){
return;
}
// 规范化
cnt++;
mx = Math.max(mx, cnt);
dfs(root.left, cnt);
dfs(root.right, cnt);
}
}// 自底向上，递归函数需要有返回值
class Solution {
public int maxDepth(TreeNode root) {
return dfs(root);
}
int dfs(TreeNode root) {
// 递归出口
if (root == null) {
return 0;
}
// 规范化
int lv = dfs(root.left);
int rv = dfs(root.right);
return Math.max(lv, rv) + 1;
}
}class Solution {
int depth = 0;
int res = 0;
public int maxDepth(TreeNode root) {
dfs(root);
return res;
}
void dfs(TreeNode root) {
if (root == null) {
return;
}
// 进来+1，并更新最大高度
depth++;
res = Math.max(res, depth);
dfs(root.left);
dfs(root.right);
// 出去-1， 维护树的高度
depth--;
}
}class Solution {
int mx = 0;
public int maxDepth(TreeNode root) {
dfs(root);
return mx;
}
int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int lv = dfs(root.left);
int rv = dfs(root.right);
// 为什么会加一？因为mx求的是最终的值，但是lv和rv是不包含根节点的，需要加上根节点
mx = Math.max(mx, Math.max(lv, rv) + 1);
return 1 + Math.max(lv, rv);
}
}404. 左叶子之和（20250327更新）
只有从左节点回到根节点的时候，我们才能确认是左节点，这个时候同时在判断是否是叶子节点（左右节点都为空）就可以了。
class Solution {
int ans = 0;
public int sumOfLeftLeaves(TreeNode root) {
// 题目求的是左叶子之和，强调的是所有叶子节点的左叶子节点
// 不是左叶子之和，不是左节点之和
dfs(root);
return ans;
}
void dfs(TreeNode root) {
if (root == null) {
return;
}
// 判断是不是叶子节点，判断是不是左节点
if (root.left != null && root.left.left == null && root.left.right == null) {
ans += root.left.val;
}
dfs(root.left);
dfs(root.right);
}
}实现力扣树构建的方式，比如给出[1,2,3,4,5], [3,9,20,null,null,15,7] 能够知道是一颗什么样子的树。
543. 二叉树的直径（20250327）
二叉树的直径就是任意两个节点的最大路径，我们只需要求到根节点左子树的最大高度，加上右子树的最大高度再加一就是我们需要的结果。
class Solution {
int mx = 0;
public int diameterOfBinaryTree(TreeNode root) {
// 左节点的最大高度+右节点的最大高度
dfs(root);
return mx;
}
int dfs(TreeNode root) {
// 这个函数是求一个节点的最大高度
if (root == null) {
return 0;
}
// 左右子树的最大高度
int lv = dfs(root.left);
int rv = dfs(root.right);
mx = Math.max(mx, lv + rv);
// 这个怎么理解？因为左右子树的最大高度是没有加上根节点的。
return 1 + Math.max(lv, rv);
}
}114. 二叉树展开为链表（20250328更新）
class Solution {
public void flatten(TreeNode root) {
dfs(root);
}
void dfs(TreeNode root) {
if (root == null) {
return;
}
// 遍历节点的左右子树
dfs(root.left);
dfs(root.right);
// 将左节点放到右节点的位置，然后把右节点放到刚才左子树的右节点上
TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
root.right = left;
// 需要定义一个p用来遍历roo提的有子树
TreeNode p = root;
while (p.right != null) {
p = p.right;
}
p.right = right;
}
}116. 填充每个节点的下一个右侧节点指针（20250328更新）
traver(l.left, l.right), traver(r.left, r.right), traver(l.right, r.left) ???
class Solution {
public Node connect(Node root) {
if (root == null) {
return root;
}
traver(root.left, root.right);
return root;
}
void traver(Node l, Node r) {
if (l == null || r == null) {
return;
}
l.next = r;
traver(l.left, l.right);
traver(r.left, r.right);
traver(l.right, r.left);
}
}112. 路径总和（20250329更新）
给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标targetSum。如果存在，返回true；否则，返回false。
129. 求根节点到叶节点数字之和（20250329更新）
给你一个二叉树的根节点root，树中每个节点都存放一个0-9的数字，每条从根到叶子节点的路径代表一个数字：
- 例如，从根节点到叶子节点的路径
1-2-3表示数字123.
计算从根节点到叶子节点生成的所有数字之和。
1448. 统计二叉树中好节点的数目（20250329）
给你一颗根为root的二叉树，请你返回二叉树中好节点的数目。
好节点X定义为：从根节点到节点X所经过的节点中，没有任何节点的值大雨X的值。
class Solution {
int cnt = 0;
public int goodNodes(TreeNode root) {
// 因为有负数，这里mx默认不能传0
dfs(root, root.val);
return cnt;
}
// mx 节点之前的最大的值
void dfs(TreeNode root, int mx) {
if (root == null) {
return;
}
if (root.val >= mx) {
cnt++;
}
mx = Math.max(mx, root.val);
dfs(root.left, mx);
dfs(root.right, mx);
}
}/**
* 向下递归的时候，维护一个参数mx，表示从根节点到当前节点之前，路径上最大的节点值
* 如果当前节点为空，到达递归边界，返回0
* 递归左子树，获取左子树的好节点个数left
* 递归右子树，获取右子树的好节点个数right
* 如果当前节点是好节点，即root.val >= mx，那么返回left+right+1, 否则返回left+right
*/
class Solution {
public int goodNodes(TreeNode root) {
return dfs(root, Integer.MIN_VALUE);
}
// 思考如何使用自底向上的方式求解？
int dfs(TreeNode root, int mx) {
if (root == null) {
return 0;
}
int left = dfs(root.left, Math.max(mx, root.val));
int right = dfs(root.right, Math.max(mx, root.val));
// 这里相当于在返回节点的时候，去判断是否是好节点
// 相当于他从上往下对每个节点维护了一个mx值，这个值就是从根节点到当前节点的最大值。
return left + right + (mx <= root.val ? 1 : 0);
}
}1.2、BFS基础
104. 二叉树的最大深度（20250326更新）
这个也可以写成BFS的形式。
BFS有三种写法，一种就是最简单的，把节点存进去然后取出来遍历，但是这一种没有办法记录层数；第二种就是通过一个for循环来记录每一层，相当于每层的权重是1；还有第三种就是节点维护自己的层级（权重）。
class Solution {
int depth = 0;
public int maxDepth(TreeNode root) {
bfs(root);
return depth;
}
void bfs(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode node = q.poll();
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
depth++;
}
}
}二、其他
1791. 找出星型图的中心节点
有一个无向的星型图，由 n 个编号从 1 到 n 的节点组成，星型图有一个中心节点，并且恰有 n-1 条边将中心节点与其他节点连接起来。
给你一个二维整数数组 edges，其中 edges[i]=[ui, vi]表示在节点之间存在一条边，请你找出返回 edges 所有表示星型图的中心节点。
根据题意，中心节点必然出现在所有的 edges[i]中，根据第一条边，判断里面的两个数据是否在后面边里面，如果在的话，就是中心节点，否则就不是中心节点。
因为题目给出 n 是大于等于 3 的，必定是大于两个节点的。
class Solution {
public int findCenter(int[][] edges) {
int a = edges[0][0], b =edges[0][1];
if(a == edges[1][0] || a == edges[1][1]){
return a;
}
else{
return b;
}
}
}1557. 可以到达所有点的最少点数目
给你一个 有向无环图， n 个节点编码为 0 到 n-1， 以及一个变数组 edges，其中 edges[i] = [from, to], 表示一条从 from 到 to 的有向边。
找到最小的点集使得从这些点出发能到达图中所有的点，题目保证解存在且唯一。
你可以以任何顺序返回这些节点的编号。
最小的点集使得能够到达图的所有点，这里我们只需要找到入度为 0 的节点就是题目的解。
class Solution {
public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
// 只有出度没有入度的节点?
int[] ans = new int[n];
for(List<Integer> dt: edges){
ans[dt.get(1)] += 1;
}
List<Integer> res = new ArrayList<>();
for(int i=0;i<ans.length;i++){
if(ans[i] == 0){
res.add(i);
}
}
return res;
}
}构建 java 列表并初始化的方式
1、List<Integer> list = Arrays.asList(1,2,3);
2、List<Integer> lit = new ArrayList<>(Arrays.asList(1,1,3));
3、List<String> lit = new ArrayList<>(Collections.singletonList("a", "b"));
图论基础及遍历算法
学习 labuladong 关于图相关的理论和知识点。
图的话和多叉树遍历类似，需要防止遍历的时候形成环，使用数据 visit 来表示每个节点是否被访问过。
图的存储的话有两种方式，一个是领接表，一个是领接矩阵，分别定义如下：
// 邻接表
List<Integer>[] graph;
// 邻接矩阵
boolean[][] graph;如果是带权图的话，邻接表存储的时候顺便把权重也存起来，邻接矩阵的话，每个坐标存的就是权重，不是 true 或者 false。
度（degree），入度（indegree）， 出度（outdegree）
矩阵（martix），顶点（vertex）
图的遍历模版：
// 记录被遍历过的节点
boolean[] visited;
// 记录从起点到当前节点的路径
boolean[] onPath;
void traverse(Graph graph, int s){
if(visited[s]){
return;
}
// 经过节点s，标记为已遍历
visited[s] = true;
// 做选择：标记节点s在路径上
onPath[s] = true;
for(int neighbor: graph.neighors(s)){
traverse(graph, neighbor);
}
// 撤销选择，节点s离开路径
onPath[s] = false;
}LCR 110. 所有可能的路径
给定一个有 n 个节点的有向无环图，用二维数组 graph 表示，请找到所有从 0 到 n-1 的路径并输出。
graph 的第 i 个数组中的单元都表示有向图 i 号节点所能够到达的下一个节点。
从 0 节点开始遍历图，将到达 n-1 的路径保存下来。
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
// 无环图
// 从 0 到 n-1的所有路径
// graph 邻接表
List<Integer> onPath = new ArrayList<>();
traverse(graph, 0, onPath);
return res;
}
// s 表示节点
public void traverse(int[][] graph, int s, List<Integer> onPath){
onPath.addLast(s);
int n = graph.length;
if(s == n-1){
res.add(new ArrayList<>(onPath));
}
for(int v: graph[s]){ // graph[s] 表示s能到达的所有节点
traverse(graph, v, onPath);
}
onPath.removeLast();
}
}547. 省份数量
这个题就是求无向图中的连通域的个数，直接 dfs/bfs。
题目给出的 isConnected 是邻接矩阵的存储方式。