【題目一】合并二叉樹
給你兩棵二叉樹：
和root1
root2
。
想象一下，當你将其中一棵覆寫到另一棵之上時，兩棵樹上的一些節點将會重疊（而另一些不會）。你需要将這兩棵樹合并成一棵新二叉樹。合并的規則是：如果兩個節點重疊，那麼将這兩個節點的值相加作為合并後節點的新值；否則，不為 null 的節點将直接作為新二叉樹的節點。
傳回合并後的二叉樹。
注意: 合并過程必須從兩個樹的根節點開始。
示例 1：
算法——DFS、BFS【練習】 示例 2：輸入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] 輸出：[3,4,5,5,4,null,7]提示：輸入：root1 = [1], root2 = [1,2] 輸出：[2,2]
- 兩棵樹中的節點數目在範圍
内[0, 2000]
-104 <= Node.val <= 104
解法一：DFS
題解：
可以使用深度優先搜尋合并兩個二叉樹。從根節點開始同時周遊兩個二叉樹，并将對應的節點進行合并。
兩個二叉樹的對應節點可能存在以下三種情況，對于每種情況使用不同的合并方式。
- 如果兩個二叉樹的對應節點都為空，則合并後的二叉樹的對應節點也為空；
- 如果兩個二叉樹的對應節點隻有一個為空，則合并後的二叉樹的對應節點為其中的非空節點；
- 如果兩個二叉樹的對應節點都不為空，則合并後的二叉樹的對應節點的值為兩個二叉樹的對應節點的值之和，此時需要顯性合并兩個節點。
對一個節點進行合并之後，還要對該節點的左右子樹分别進行合并。這是一個遞歸的過程。
代碼實作：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1 == null) {
return root2;
}
if(root2 == null) {
return root1;
}
TreeNode root3 = new TreeNode(root1.val + root2.val);
root3.left = mergeTrees(root1.left , root2.left);
root3.right = mergeTrees(root1.right , root2.right);
return root3;
}
}
解法二：BFS
題解：
也可以使用廣度優先搜尋合并兩個二叉樹。首先判斷兩個二叉樹是否為空，如果兩個二叉樹都為空，則合并後的二叉樹也為空，如果隻有一個二叉樹為空，則合并後的二叉樹為另一個非空的二叉樹。
如果兩個二叉樹都不為空，則首先計算合并後的根節點的值，然後從合并後的二叉樹與兩個原始二叉樹的根節點開始廣度優先搜尋，從根節點開始同時周遊每個二叉樹，并将對應的節點進行合并。
使用三個隊列分别存儲合并後的二叉樹的節點以及兩個原始二叉樹的節點。初始時将每個二叉樹的根節點分别加入相應的隊列。每次從每個隊列中取出一個節點，判斷兩個原始二叉樹的節點的左右子節點是否為空。如果兩個原始二叉樹的目前節點中至少有一個節點的左子節點不為空，則合并後的二叉樹的對應節點的左子節點也不為空。對于右子節點同理。
如果合并後的二叉樹的左子節點不為空，則需要根據兩個原始二叉樹的左子節點計算合并後的二叉樹的左子節點以及整個左子樹。考慮以下兩種情況：
- 如果兩個原始二叉樹的左子節點都不為空，則合并後的二叉樹的左子節點的值為兩個原始二叉樹的左子節點的值之和，在建立合并後的二叉樹的左子節點之後，将每個二叉樹中的左子節點都加入相應的隊列；
- 如果兩個原始二叉樹的左子節點有一個為空，即有一個原始二叉樹的左子樹為空，則合并後的二叉樹的左子樹即為另一個原始二叉樹的左子樹，此時也不需要對非空左子樹繼續周遊，是以不需要将左子節點加入隊列。
對于右子節點和右子樹，處理方法與左子節點和左子樹相同。
代碼實作：
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) {
return t2;
}
if (t2 == null) {
return t1;
}
TreeNode merged = new TreeNode(t1.val + t2.val);
Queue<TreeNode> queue = new LinkedList<TreeNode>();
Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
queue.offer(merged);
queue1.offer(t1);
queue2.offer(t2);
while (!queue1.isEmpty() && !queue2.isEmpty()) {
TreeNode node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
TreeNode left1 = node1.left, left2 = node2.left, right1 = node1.right, right2 = node2.right;
if (left1 != null || left2 != null) {
if (left1 != null && left2 != null) {
TreeNode left = new TreeNode(left1.val + left2.val);
node.left = left;
queue.offer(left);
queue1.offer(left1);
queue2.offer(left2);
} else if (left1 != null) {
node.left = left1;
} else if (left2 != null) {
node.left = left2;
}
}
if (right1 != null || right2 != null) {
if (right1 != null && right2 != null) {
TreeNode right = new TreeNode(right1.val + right2.val);
node.right = right;
queue.offer(right);
queue1.offer(right1);
queue2.offer(right2);
} else if (right1 != null) {
node.right = right1;
} else {
node.right = right2;
}
}
}
return merged;
}
}
【題目二】圖像渲染
有一幅以二維整數數組表示的圖畫，每一個整數表示該圖畫的像素值大小，數值在 0 到 65535 之間。
給你一個坐标
表示圖像渲染開始的像素值（行 ，列）和一個新的顔色值(sr, sc)
newColor
，讓你重新上色這幅圖像。
為了完成上色工作，從初始坐标開始，記錄初始坐标的上下左右四個方向上像素值與初始坐标相同的相連像素點，接着再記錄這四個方向上符合條件的像素點與他們對應四個方向上像素值與初始坐标相同的相連像素點，……，重複該過程。将所有有記錄的像素點的顔色值改為新的顔色值。
最後傳回經過上色渲染後的圖像。
示例 1:
注意:輸入: image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1, sc = 1, newColor = 2 輸出: [[2,2,2],[2,2,0],[2,0,1]] 解析: 在圖像的正中間，(坐标(sr,sc)=(1,1)), 在路徑上所有符合條件的像素點的顔色都被更改成2。 注意，右下角的像素沒有更改為2， 因為它不是在上下左右四個方向上與初始點相連的像素點。
和image
的長度在範圍image[0]
内。[1, 50]
- 給出的初始點将滿足
和0 <= sr < image.length
。0 <= sc < image[0].length
和image[i][j]
表示的顔色值在範圍newColor
内。[0, 65535]
思路：
我們從給定的起點開始，進行深度優先搜尋。每次搜尋到一個方格時，如果其與初始位置的方格顔色相同，就将該方格的顔色更新，以防止重複搜尋；如果不相同，則進行回溯。
代碼實作：
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
if(image[sr][sc] != newColor)
dfs(image , sr , sc , newColor , image[sr][sc]);
return image;
}
public void dfs(int[][] image ,int i ,int j ,int newColor , int oldColor) {
if(i >= 0 && j >= 0 && i < image.length && j < image[0].length) {
if(image[i][j] == oldColor) {
image[i][j] = newColor;
dfs(image,i + 1,j,newColor,oldColor);
dfs(image,i - 1,j,newColor,oldColor);
dfs(image,i,j + 1,newColor,oldColor);
dfs(image,i,j - 1,newColor,oldColor);
}
}
}
}
【題目三】島嶼的最大面積
給你一個大小為
的二進制矩陣m x n
grid
。
島嶼 是由一些相鄰的
(代表土地) 構成的組合，這裡的「相鄰」要求兩個1
必須在 水準或者豎直的四個方向上 相鄰。你可以假設1
的四個邊緣都被grid
（代表水）包圍着。
島嶼的面積是島上值為
1
的單元格的數目。
計算并傳回
中最大的島嶼面積。如果沒有島嶼，則傳回面積為grid
。
示例 1：
算法——DFS、BFS【練習】 示例 2：輸入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] 輸出：6 解釋：答案不應該是11，因為島嶼隻能包含水準或垂直這四個方向上的1。提示：輸入：grid = [[0,0,0,0,0,0,0,0]] 輸出：0
m == grid.length
n == grid[i].length
1 <= m, n <= 50
為 或grid[i][j]
1
思路：
我們想知道網格中每個連通形狀的面積，然後取最大值。
如果我們在一個土地上，以 44 個方向探索與之相連的每一個土地（以及與這些土地相連的土地），那麼探索過的土地總數将是該連通形狀的面積。
為了確定每個土地通路不超過一次，我們每次經過一塊土地時，将這塊土地的值置為 00。這樣我們就不會多次通路同一土地。
代碼實作：
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int n = grid.length;//行數
int m = grid[0].length;//列數
int max = 0;//最大島嶼面積
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
if(grid[i][j] == 1) {
max = Math.max(DFS(grid,i,j,n,m),max);
}
}
}
return max;
}
public int DFS(int[][] grid,int i,int j,int n,int m) {
if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] != 1)
return 0;
grid[i][j] = 0;
int count = 1;
count += DFS(grid,i - 1,j,n,m);
count += DFS(grid,i + 1,j,n,m);
count += DFS(grid,i,j - 1,n,m);
count += DFS(grid,i,j + 1,n,m);
return count;
}
}