java数据结构与算法刷题-----LeetCode617. 合并二叉树

本文主要是介绍java数据结构与算法刷题-----LeetCode617. 合并二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;//两个结点都为空，返回nullif(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;}
}