Java

  • /**
    
     Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
    
     You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
    
     Example 1:
     Input:
     Tree 1                     Tree 2
            1                         2
           / \                       / \
          3   2                     1   3
         /                           \   \
        5                             4   7
    
     Output:
     Merged tree:
        3
       / \
      4   5
     / \   \
    5   4   7
     Note: The merging process must start from the root nodes of both trees.
    
     */
    public class Merge_Two_Binary_Trees {
        /**
         * Definition for a binary tree node.
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode(int x) { val = x; }
         * }
         */
        class Solution {
            public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    
                TreeNode result = null;
    
                if (t1 == null && t2 == null) {
                    return result;
                }
    
                /*
                    input:
    
                    [1,2,null,3]
                    [1,null,2,null,3]
                 */
                if (t1 != null && t2 == null) { //@note @memorize t1 may have children
                    result = new TreeNode(t1.val);
    
                    result.left = mergeTrees(t1.left, null);
                    result.right = mergeTrees(t1.right, null);
                }
    
                if (t1 == null && t2 != null) {
                    result = new TreeNode(t2.val);
    
                    result.left = mergeTrees(null, t2.left);
                    result.right = mergeTrees(null, t2.right);
                }
    
                if (t1 != null && t2 != null) {
                    result = new TreeNode(t1.val + t2.val);
    
                    result.left = mergeTrees(t1.left, t2.left);
                    result.right = mergeTrees(t1.right, t2.right);
                }
    
                return result;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/merge-two-binary-trees
    // Time: O(N)
    // Space: O(H)
    class Solution {
    public:
        TreeNode* mergeTrees(TreeNode* a, TreeNode* b) {
            if (!a || !b) return a ? a : b;
            auto node = new TreeNode(a->val + b->val);
            node->left = mergeTrees(a->left, b->left);
            node->right = mergeTrees(a->right, b->right);
            return node;
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
      def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        if t1 or t2:
          root = TreeNode((t1 and t1.val or 0) + (t2 and t2.val or 0))
          root.left = self.mergeTrees(t1 and t1.left, t2 and t2.left)
          root.right = self.mergeTrees(t1 and t1.right, t2 and t2.right)
          return root
    
    

Java

  • /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
            if (t1 == null && t2 == null)
                return null;
            if (t1 == null)
                return t2;
            if (t2 == null)
                return t1;
            TreeNode mergeRoot = 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(mergeRoot);
            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;
                TreeNode right1 = node1.right, right2 = node2.right;
                if (left1 != null && left2 != null) {
                    TreeNode mergeLeft = new TreeNode(left1.val + left2.val);
                    node.left = mergeLeft;
                    queue.offer(mergeLeft);
                    queue1.offer(left1);
                    queue2.offer(left2);
                } else if (left1 != null) {
                    TreeNode mergeLeft = new TreeNode(left1.val);
                    node.left = mergeLeft;
                    queue.offer(mergeLeft);
                    queue1.offer(left1);
                    queue2.offer(new TreeNode(0));
                } else if (left2 != null) {
                    TreeNode mergeLeft = new TreeNode(left2.val);
                    node.left = mergeLeft;
                    queue.offer(mergeLeft);
                    queue1.offer(new TreeNode(0));
                    queue2.offer(left2);
                }
                if (right1 != null && right2 != null) {
                    TreeNode mergeRight = new TreeNode(right1.val + right2.val);
                    node.right = mergeRight;
                    queue.offer(mergeRight);
                    queue1.offer(right1);
                    queue2.offer(right2);
                } else if (right1 != null) {
                    TreeNode mergeRight = new TreeNode(right1.val);
                    node.right = mergeRight;
                    queue.offer(mergeRight);
                    queue1.offer(right1);
                    queue2.offer(new TreeNode(0));
                } else if (right2 != null) {
                    TreeNode mergeRight = new TreeNode(right2.val);
                    node.right = mergeRight;
                    queue.offer(mergeRight);
                    queue1.offer(new TreeNode(0));
                    queue2.offer(right2);
                }
            }
            return mergeRoot;
        }
    }
    
  • // OJ: https://leetcode.com/problems/merge-two-binary-trees
    // Time: O(N)
    // Space: O(H)
    class Solution {
    public:
        TreeNode* mergeTrees(TreeNode* a, TreeNode* b) {
            if (!a || !b) return a ? a : b;
            auto node = new TreeNode(a->val + b->val);
            node->left = mergeTrees(a->left, b->left);
            node->right = mergeTrees(a->right, b->right);
            return node;
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
      def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        if t1 or t2:
          root = TreeNode((t1 and t1.val or 0) + (t2 and t2.val or 0))
          root.left = self.mergeTrees(t1 and t1.left, t2 and t2.left)
          root.right = self.mergeTrees(t1 and t1.right, t2 and t2.right)
          return root
    
    

All Problems

All Solutions