[LeetCode][617. Merge Two Binary Trees] 4 Approaches: Recursion, Iteration, BFS and DFS

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 6.4k 阅读时长 ≈ 6 分钟

By Long Luo

This article is the solution 4 Approaches: Recursion, Iteration, BFS and DFS of Problem 617. Merge Two Binary Trees.

Here are 4 approaches to solve this problem in Java: Recursion, Iteration, BFS and DFS.

Recursion

Method 1: New Tree

We can create a new Tree, each \(\texttt{TreeNode}\) value is sum of two nodes.

1
2
3
4
5
6
7
8
9
10
11
12
public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    }
    if (root2 == null) {
        return root1;
    }
    TreeNode merged = new TreeNode(root1.val + root2.val);
    merged.left = mergeTrees(root1.left, root2.left);
    merged.right = mergeTrees(root1.right, root2.right);
    return merged;
}

Analysis

  • Time Complexity: \(O(min(m, n))\)
  • Space Complexity: \(O(min(m, n))\)

Method 2

Traverse both the given trees in a PreOrder style.

At every step, check if the current node exists for both the trees. If one of these children happens to be null, we return the child of the other tree to be added as a child subtree to the calling parent node in the first tree.

We can add the values in the current nodes of both the trees and update the value in the current node of the first tree to reflect this sum obtained.

Then we call the \(\texttt{mergeTrees()}\) with the left children and then with the right children of the current nodes of the two trees.

At the end, the first tree will represent the required resultant merged binary tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static TreeNode mergeTrees_rec(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    }
    if (root2 == null) {
        return root1;
    }

    if (root1 != null) {
        root1.val += root2.val;
        root1.left = mergeTrees_rec(root1.left, root2.left);
        root1.right = mergeTrees_rec(root1.right, root2.right);
    }

    return root1;
}

Analysis

  • Time Complexity: \(O(min(m, n))\)
  • Space Complexity: \(O(min(m, n))\)

Iteration

We can also traverse the two trees by make use of a stack to do so.

Each entry in the Stack strores data in the form \([\textit{node}_{tree1}, \textit{node}_{tree2}]\).

  1. We push the root nodes of both the trees onto the stack.
  2. At every step, we remove a node pair from the top of the stack.
  3. For every node pair removed, we add the values corresponding to the two nodes and update the value of the corresponding node in the first tree.
  4. If \(root1.left != null && root2.left != null\), we push the left child(pair) of both the trees onto the stack.
  5. If \(root1.left == null\), we append the left child(subtree) of the second tree to the current node of the first tree. We do the same for the right child pair as well.
  6. If, at any step, both the current nodes are null, we continue with popping the next nodes from the stack.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public TreeNode mergeTrees_iter(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    } else if (root2 == null) {
        return root1;
    }

    Deque<TreeNode[]> stack = new ArrayDeque<>();
    stack.push(new TreeNode[]{root1, root2});
    while (!stack.isEmpty()) {
        TreeNode[] currNodes = stack.pop();
        if (currNodes[0] == null || currNodes[1] == null) {
            continue;
        }

        currNodes[0].val += currNodes[1].val;
        if (currNodes[0].left == null) {
            currNodes[0].left = currNodes[1].left;
        } else {
            stack.push(new TreeNode[]{currNodes[0].left, currNodes[1].left});
        }

        if (currNodes[0].right == null) {
            currNodes[0].right = currNodes[1].right;
        } else {
            stack.push(new TreeNode[]{currNodes[0].right, currNodes[1].right});
        }
    }

    return root1;
}

Analysis

  • Time Complexity: \(O(min(m, n))\)
  • Space Complexity: \(O(min(m, n))\)

BFS

BFS is like the Iteration method, it create a new Tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public static TreeNode mergeTrees_bfs(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    } else 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 = queue1.poll();
        TreeNode node2 = queue2.poll();
        if (node1.left != null || node2.left != null) {
            if (node1.left != null && node2.left != null) {
                TreeNode leftNode = new TreeNode(node1.left.val + node2.left.val);
                node.left = leftNode;
                queue.offer(leftNode);
                queue1.offer(node1.left);
                queue2.offer(node2.left);
            } else if (node1.left != null) {
                node.left = node1.left;
            } else if (node2.left != null) {
                node.left = node2.left;
            }
        }

        if (node1.right != null || node2.right != null) {
            if (node1.right != null && node2.right != null) {
                TreeNode rightNode = new TreeNode(node1.right.val + node2.right.val);
                node.right = rightNode;
                queue.offer(rightNode);
                queue1.offer(node1.right);
                queue2.offer(node2.right);
            } else if (node1.right != null) {
                node.right = node1.right;
            } else if (node2.right != null) {
                node.right = node2.right;
            }
        }
    }

    return merged;
}

The BFS code is not neat, I have refactor it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    } else if (root2 == null) {
        return root1;
    }

    Queue<TreeNode[]> queue = new LinkedList<>();
    queue.offer(new TreeNode[]{root1, root2});
    while (!queue.isEmpty()) {
        TreeNode[] node = queue.poll();
        node[0].val += node[1].val;

        if (node[0].left != null || node[1].left != null) {
            if (node[0].left != null && node[1].left != null) {
                queue.offer(new TreeNode[]{node[0].left, node[1].left});
            } else if (node[0].left == null) {
                node[0].left = node[1].left;
            }
        }

        if (node[0].right != null || node[1].right != null) {
            if (node[0].right != null && node[1].right != null) {
                queue.offer(new TreeNode[]{node[0].right, node[1].right});
            } else if (node[0].right == null) {
                node[0].right = node[1].right;
            }
        }
    }

    return root1;
}

Analysis

  • Time Complexity: \(O(min(m, n))\)
  • Space Complexity: \(O(min(m, n))\)

DFS

DFS is the same as the recursion method, just a little bit difference.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static TreeNode mergeTrees_dfs(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    }
    dfs(root1, root2);
    return root1;
}

public static void dfs(TreeNode root1, TreeNode root2) {
    if (root1 != null && root2 != null) {
        if (root1 != root2) {
            root1.val += root2.val;
        }

        if (root1.left == null) {
            root1.left = root2.left;
        }
        if (root1.right == null) {
            root1.right = root2.right;
        }
			
        dfs(root1.left, root2.left);
        dfs(root1.right, root2.right);
    }
}

Analysis

  • Time Complexity: \(O(min(m, n))\)
  • Space Complexity: \(O(min(m, n))\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗