Skip to content

617.merge-two-binary-trees.md

Latest commit

 

History

History
119 lines (107 loc) · 2.95 KB

617.merge-two-binary-trees.md

File metadata and controls

119 lines (107 loc) · 2.95 KB

617. Merge Two Binary Trees

Test Cases

Normal Cases

Input: 
        1               9
      /   \           /   \
     3     5         4     10
    /     / \         \      \
   7     2  -1         1      5
        /   /                / \
       8   -2              16   77
            \
             888
Output: 
        10
      /    \
     7      15
    / \     / \
   7  1    2   4
          /   /  \
         8   14  77
              \
              888

Edge / Corner Cases

  • Two tree with different structures, the nodes exist in one tree but don't exist in another tree.
Input: 
        1           2        
      /   \       /   \
     3     3     4     4
    /     /       \     \
   5     5         6     6
    \   /          /      \
     7 7          8        8
Output: 
        3
      /   \
     7     7
   /  \   /  \
  5    6 5    6
   \   / /     \
    7 8 7       8
  • One tree is empty and another is not empty.
Input:
    1       []
   / \
  2   3

Output:
    1
   / \
  2   3

Recursive

fun mergeTrees(root1: TreeNode?, root2: TreeNode?): TreeNode? {
    if (root1 == null && root2 == null) return null
    if (root1 == null) return root2
    if (root2 == null) return root1

    val newRoot = TreeNode(root1.`val` + root2.`val`)
    newRoot.left = mergeTrees(root1.left, root2.left)
    newRoot.right = mergeTrees(root1.right, root2.right)

    return newRoot
}
  • Time Complexity: O(min(m + n)) where m and n represents the nodes of two trees.
  • Space Complexity: O(min(m + n)).

Iterative

  1. We use root1 as the merged tree, and merge root2 into root1.
  2. We can use queue or stack to store the nodes to be merged.
  3. We enqueue only when the node in root1 is not empty.
  4. If root1 is empty, we just attach the node in root2 into root1 and skip enqueuing.
fun mergeTrees(root1: TreeNode?, root2: TreeNode?): TreeNode? {
    if (root1 == null) return root2
    if (root2 == null) return root1

    val q1 = ArrayDeque<TreeNode>()
    val q2 = ArrayDeque<TreeNode>()
    q1.addLast(root1)
    q2.addLast(root2)
    while (q1.isNotEmpty() && q2.isNotEmpty()) {
        val n1 = q1.removeFirst()
        val n2 = q2.removeFirst()
        n1.`val` += n2.`val`

        // If the node in first tree is empty, just merge the node in second tree
        // We don't need to enqueue the node, because the node is already merged.
        if (n1.left == null) {
            n1.left = n2.left
        } else if (n2.left != null) {
            q1.addLast(n1.left)
            q2.addLast(n2.left)
        }

        if (n1.right == null) {
            n1.right = n2.right
        } else if (n2.right != null) {
            q1.addLast(n1.right)
            q2.addLast(n2.right)
        }
    }
    return root1
}
  • Time Complexity: O(min(m + n)) where m and n represents the nodes of two trees.
  • Space Complexity: O(min(m + n)).