617. 合并二叉树

相应位置数字相加。
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7

深度遍历

  1.     public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
  2.         if(t1 == null){
  3.             return t2;
  4.         }
  5.         if(t2 == null){
  6.             return t1;
  7.         }
  8.         TreeNode merged = new TreeNode(t1.val + t2.val);
  9.         merged.left = mergeTrees(t1.left, t2.left);
  10.         merged.right = mergeTrees(t1.right, t2.right);
  11.         return merged;
  12. // 作者：LeetCode-Solution
  13. // 链接：https://leetcode-cn.com/problems/merge-two-binary-trees/solution/he-bing-er-cha-shu-by-leetcode-solution/
  14.     }

广度优先遍历

  1.     public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
  2.         if (t1 == null) {
  3.             return t2;
  4.         }
  5.         if (t2 == null) {
  6.             return t1;
  7.         }
  8.         TreeNode merged = new TreeNode(t1.val + t2.val);
  9.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  10.         Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
  11.         Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
  12.         queue.offer(merged);
  13.         queue1.offer(t1);
  14.         queue2.offer(t2);
  15.         while (!queue1.isEmpty() && !queue2.isEmpty()) {
  16.             TreeNode node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
  17.             TreeNode left1 = node1.left, left2 = node2.left, right1 = node1.right, right2 = node2.right;
  18.             if (left1 != null || left2 != null) {
  19.                 if (left1 != null && left2 != null) {
  20.                     TreeNode left = new TreeNode(left1.val + left2.val);
  21.                     node.left = left;
  22.                     queue.offer(left);
  23.                     queue1.offer(left1);
  24.                     queue2.offer(left2);
  25.                 } else if (left1 != null) {
  26.                     node.left = left1;
  27.                 } else if (left2 != null) {
  28.                     node.left = left2;
  29.                 }
  30.             }
  31.             if (right1 != null || right2 != null) {
  32.                 if (right1 != null && right2 != null) {
  33.                     TreeNode right = new TreeNode(right1.val + right2.val);
  34.                     node.right = right;
  35.                     queue.offer(right);
  36.                     queue1.offer(right1);
  37.                     queue2.offer(right2);
  38.                 } else if (right1 != null) {
  39.                     node.right = right1;
  40.                 } else {
  41.                     node.right = right2;
  42.                 }
  43.             }
  44.         }
  45.         return merged;
  46.    }
  47. 作者：LeetCode-Solution
  48. 链接：https://leetcode-cn.com/problems/merge-two-binary-trees/solution/he-bing-er-cha-shu-by-leetcode-solution/
  49. 来源：力扣（LeetCode）
  50. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。