617. Merge Two Binary Trees 发表于 2022-01-11 DFS123456789101112131415class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1 == null) { return root2; } else if (root2 == null) { return root1; } TreeNode root = new TreeNode(root1.val + root2.val); root.left = mergeTrees(root1.left, root2.left); root.right = mergeTrees(root1.right, root2.right); return root; }} BFS123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1 == null) { return root2; } else if (root2 == null) { return root1; } TreeNode node = new TreeNode(root1.val + root2.val); Queue<TreeNode> queue = new LinkedList<>(); Queue<TreeNode> queue1 = new LinkedList<>(); Queue<TreeNode> queue2 = new LinkedList<>(); queue.add(node); queue1.add(root1); queue2.add(root2); while (!queue1.isEmpty() && !queue2.isEmpty()) { TreeNode mergedRoot = queue.poll(), leftRoot = queue1.poll(), rightRoot = queue2.poll(); TreeNode left1 = leftRoot.left, right1 = leftRoot.right; TreeNode left2 = rightRoot.left, right2 = rightRoot.right; if (left1 != null || left2 != null) { if (left1 != null && left2 != null) { TreeNode left = new TreeNode(left1.val + left2.val); mergedRoot.left = left; queue.add(left); queue1.add(left1); queue2.add(left2); } else if (left1 != null) { mergedRoot.left = left1; } else if (left2 != null) { mergedRoot.left = left2; } } if (right1 != null || right2 != null) { if (right1 != null && right2 != null) { TreeNode right = new TreeNode(right1.val + right2.val); mergedRoot.right = right; queue.add(right); queue1.add(right1); queue2.add(right2); } else if (right1 != null) { mergedRoot.right = right1; } else if (right2 != null) { mergedRoot.right = right2; } } } return node; }} Reference617. Merge Two Binary Trees