I like to read this solution as a small machine: keep the useful information, throw away the noise. For 617. Merge Two Binary Trees, the solution in this repository is mainly a sliding window solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: sliding window.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are mergeTrees.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Given 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.
03
04You 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.
05
06Example 1:
07
08Input:
09 Tree 1 Tree 2
10 1 2
11 / \ / \
12 3 2 1 3
13 / \ \
14 5 4 7
15Output:
16Merged tree:
17 3
18 / \
19 4 5
20 / \ \
21 5 4 7
22
23
24Note: The merging process must start from the root nodes of both trees.
25**/
26
27/**
28 * Definition for a binary tree node.
29 * struct TreeNode {
30 * int val;
31 * TreeNode *left;
32 * TreeNode *right;
33 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
34 * };
35 */
36
37//Your runtime beats 94.23 % of cpp submissions.
38class Solution {
39public:
40 TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
41 //add the values of t2 onto t1
42 if(t1==NULL){
43 return t2;
44 }else if(t2==NULL){
45 return t1;
46 }else{ //t1!=NULL && t2!=NULL
47 //use t1 as final result
48 t1->val += t2->val;
49 t1->left = mergeTrees(t1->left, t2->left);
50 t1->right = mergeTrees(t1->right, t2->right);
51 return t1;
52 }
53 }
54};
55
56/**
57Approach #1 Using Recursion [Accepted]
58We can traverse both the given trees in a preorder fashion. At every step, we check if the current node exists(isn't null) for both the trees. If so, we 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. At every step, we also call the original function mergeTrees() with the left children and then with the right children of the current nodes of the two trees. If at any step, one of these children happens to be null, we return the child of the other tree(representing the corresponding child subtree) to be added as a child subtree to the calling parent node in the first tree. At the end, the first tree will represent the required resultant merged binary tree.
59
60The following animation illustrates the process.
61
62//Java
63/**
64 * Definition for a binary tree node.
65 * public class TreeNode {
66 * int val;
67 * TreeNode left;
68 * TreeNode right;
69 * TreeNode(int x) { val = x; }
70 * }
71 */
72public class Solution {
73 public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
74 if (t1 == null)
75 return t2;
76 if (t2 == null)
77 return t1;
78 t1.val += t2.val;
79 t1.left = mergeTrees(t1.left, t2.left);
80 t1.right = mergeTrees(t1.right, t2.right);
81 return t1;
82 }
83}
84Complexity Analysis
85
86Time complexity : O(m). A total of mm nodes need to be traversed. Here, m represents the minimum number of nodes from the two given trees.
87
88Space complexity : O(m). The depth of the recursion tree can go upto m in the case of a skewed tree. In average case, depth will be O(logm).
89**/
90
91/**
92Approach #2 Iterative Method [Accepted]
93Algorithm
94
95In the current approach, we again traverse the two trees,
96but this time we make use of a stackstack to do so instead of making use of recursion.
97Each entry in the stackstack strores data in the form [node_{tree1}, node_{tree2}].
98Here, node_{tree1} and node_{tree2} are the nodes of the first tree and the second tree respectively.
99
100We start off by pushing the root nodes of both the trees onto the stackstack.
101Then, at every step, we remove a node pair from the top of the stack.
102For every node pair removed, we add the values corresponding to the two nodes and
103update the value of the corresponding node in the first tree.
104Then, if the left child of the first tree exists,
105we push the left child(pair) of both the trees onto the stack.
106If the left child of the first tree doesn't exist,
107we append the left child(subtree) of the second tree to the current node of the first tree.
108We do the same for the right child pair as well.
109
110If, at any step, both the current nodes are null, we continue with popping the next nodes from the stackstack.
111
112The following animation depicts the process.
113
114//Java
115/**
116 * Definition for a binary tree node.
117 * public class TreeNode {
118 * int val;
119 * TreeNode left;
120 * TreeNode right;
121 * TreeNode(int x) { val = x; }
122 * }
123 */
124public class Solution {
125 public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
126 if (t1 == null)
127 return t2;
128 Stack < TreeNode[] > stack = new Stack < > ();
129 stack.push(new TreeNode[] {t1, t2});
130 while (!stack.isEmpty()) {
131 TreeNode[] t = stack.pop();
132 if (t[0] == null || t[1] == null) {
133 continue;
134 }
135 t[0].val += t[1].val;
136 if (t[0].left == null) {
137 t[0].left = t[1].left;
138 } else {
139 stack.push(new TreeNode[] {t[0].left, t[1].left});
140 }
141 if (t[0].right == null) {
142 t[0].right = t[1].right;
143 } else {
144 stack.push(new TreeNode[] {t[0].right, t[1].right});
145 }
146 }
147 return t1;
148 }
149}
150
151Complexity Analysis
152
153Time complexity : O(n). We traverse over a total of nn nodes. Here, n refers to the smaller of the number of nodes in the two trees.
154
155Space complexity : O(n). The depth of stack can grow upto nn in case of a skewed tree.
156**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.