路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
class Solution {
List<List<Integer>> res = new ArrayList<>();
int targetSum = 0;
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
this.targetSum = targetSum;
dfs(root, new Stack<>());
return res;
}
public void dfs(TreeNode node, Stack<Integer> stack) {
if (node == null) {
return;
}
stack.push(node.val);
dfs(node.left, stack);
dfs(node.right, stack);
if (node.left == null && node.right == null && stack.stream().mapToInt(it -> it).sum() == targetSum) {
res.add(new ArrayList<>(stack));
}
stack.pop();
}
}
114. 二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
class Solution {
public void flatten(TreeNode root) {
dfs(root);
}
public void dfs(TreeNode node) {
if (node == null) {
return;
}
if (node.left != null) {
TreeNode lastRight = node.right;
node.right = node.left;
node.left = null;
if (lastRight != null) {
TreeNode right = node.right;
while (right.right != null) {
right = right.right;
}
right.right = lastRight;
}
}
dfs(node.left);
dfs(node.right);
}
}
116. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，‘#’ 标志着每一层的结束。
class Solution {
public Node connect(Node root) {
if (root == null || root.left == null) {
return root;
}
root.left.next = root.right;
if (root.next != null) {
root.right.next = root.next.left;
}
connect(root.left);
connect(root.right);
return root;
}
}
图像渲染
有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
最后返回 经过上色渲染后的图像 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/flood-fill
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int startColor = image[sr][sc];
if (startColor == color) {
return image;
}
dfs(image, new int[]{sr, sc}, color, startColor);
image[sr][sc] = color;
return image;
}
public void dfs(int[][] image, int[] curIndex, int color, int startColor) {
for (int i = 0; i < 4; i++) {
int nextX = curIndex[0] + dx[i], nextY = curIndex[1] + dy[i];
if (nextX >= 0 && nextX < image.length && nextY >= 0 && nextY < image[0].length && image[nextX][nextY] == startColor) {
image[nextX][nextY] = color;
dfs(image, new int[]{nextX, nextY}, color, startColor);
}
}
}
}
695. 岛屿的最大面积
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/max-area-of-island
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
public int maxAreaOfIsland(int[][] grid) {
int num = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
num = Math.max(num, dfs(i, j, grid));
}
}
}
return num;
}
public int dfs(int x, int y, int[][] grid) {
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) {
return 0;
}
grid[x][y] = 0;
int num = 1;
for (int i = 0; i < 4; i++) {
num += dfs(x + dx[i], y + dy[i], grid);
}
return num;
}
}