如果考虑递归,就需要知道递归的终止条件是什么?本题的终止条件是:
if(root1 == null) return root2; if(root2 == null) return root1;
class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if(root1 == null) return root2; if(root2 == null) return root1; TreeNode root = new TreeNode(root1.val+root2.val);//节点的val值进行合并 root.left = mergeTrees(root1.left,root2.left);//左子树进行合并 root.right = mergeTrees(root1.right,root2.right);//右子树进行合并 return root; } }
使用队列来模拟层序遍历,可以将两棵树的节点放入到队列中。
class Solution{ public TreeNode mergeTrees(TreeNode root1,TreeNode root2){ if(root1 == null) return root2; if(root2 == null) return root1; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root1); queue.offer(root2); while(!queue.isEmpty()){ TreeNode node1 = queue.peek(); queue.poll(); TreeNode node2 = queue.peek(); queue.poll(); node1.val += node2.val; if(node1.left != null && node2.left != null){ queue.offer(node1.left); queue.offer(node2.left); } if(node1.right != null && node2.right != null){ queue.offer(node1.right); queue.offer(node2.right); } if(node1.left == null && node2.left != null){ node1.left = node2.left; } if(node1.right == null && node2.right != null){ node1.right = node2.right; } } return root1; } }
取三个队列容器,构建一个新的节点,将他输入到queue,通过队列弹出poll每次更新TreeNode,即node,node1,node2.从而左右子树都会更新 。
class Solution{ public TreeNode mergeTrees(TreeNode root1,TreeNode root2){ if(root1 == null) return root2; if(root2 == null) return root1; TreeNode merged = new TreeNode(root1.val+root2.val); Queue<TreeNode> queue = new LinkedList<>(); Queue<TreeNode> queue1 = new LinkedList<>(); Queue<TreeNode> queue2 = new LinkedList<>(); queue.offer(merged); queue1.offer(root1); queue2.offer(root2); while(!queue1.isEmpty() && !queue2.isEmpty()){ TreeNode node = queue.poll(); TreeNode node1 = queue.poll(); TreeNode node2 = queue.poll(); TreeNode left1 = node1.left; TreeNode left2 = node2.left; TreeNode rigth1 = node1.right; TreeNode 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 if(right2 != null){ node.right = right2; } } } } }