| java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846 |
|---|
| 解题思路 |
|---|
- 此题如果使用广度优先遍历，一定需要创建很多队列，代码量也会很多。所以选择深度优先。但是广度优先代码也会给出
- 从根结点开始依次合并，如果当前合并位置有一个为null，那么直接等于另一个即可
- 如果两个都不为null，那么将他俩的val值相加。最终返回相加后的结点
| 代码 |
|---|
- 深度优先
/**
* 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 && root2 == null) return null;//两个结点都为空，返回null
if(root1 == null) return root2;//如果root1为空，那么直接返回root2，将root2放在当前应该合并位置
if(root2 == null) return root1;//如果root2为空，那么直接返回root1，将root1放在当前应该合并位置
//如果两个结点都存在
root1.val += root2.val;//则合并
root1.left = mergeTrees(root1.left,root2.left);//左子树合并
root1.right = mergeTrees(root1.right,root2.right); //右子树合并
return root1;//返回合并后的结点，最终递归完成后，一定返回根节点。
}
}
- 广度优先
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;
}
}
