preface

Morning when answer the following questions are written [LeetCode94 title sequence in the binary tree traversal] brush | punch, the antithesis to everybody simple introduced the binary tree traversal ways, why call before the order, in sequence, after the sequence traversal, interested or want to know can go to see the 😄 😄 😄

Topic describes

Title address: 617. Merging binary trees

Given two binary trees, imagine that when you overlay one of them on top of the other, some nodes of the two binary trees will overlap.

You need to merge them into a new binary tree. The rule for merging is that if two nodes overlap, their values are added as the new value of the nodes merged, otherwise a node that is not NULL is directly added as a node in the new binary 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 7Copy the code

Note: The merge must start at the root of both trees.

Their thinking

[LeetCode94 questions before order in the binary tree traversal] | brush topic because the topic request in the clock is in the sequence traversal, so use is in the sequence traversal.

Given two binary trees T1 and T2, to merge the binary tree, we directly use the preceding traversal recursive implementation. (You can use whichever recursion you want here.)

So we’re going to merge T2 onto T1.

The first step is to merge the two binary trees. We need to make a judgment of the situation first, not to start recursion directly, but to judge T1 and T2 first: if -T1 is empty, we will return T2, regardless of whether T2 is empty (if T2 is empty, it will return t2, so we don’t care about T2 here). – return t1 if t2 is empty (t1 is definitely not empty after the previous step).

In the second step, after the judgment step, it is proved that t1 and T2 nodes are definitely not empty, and t1.val + t2.val is used to cover t1.val to realize the combination of values of overlapping nodes required in the question.

Step 3, because we said to use the prior traversal, we recursively traverse the left subtrees of T1 and T2, repeating steps 1 and 2 will merge the values of their left subtrees.

Step 4 recursively traverses the right subtrees of T1 and T2. Repeat steps 1 and 2 to merge the values of their right subtrees.

And finally, we just go back to T1. (Since we are merging T2 to T1, return T1).

The problem solving code

var mergeTrees = function(t1, t2) { if(! t1) return t2; if(! t2) return t1; t1.val = t1.val + t2.val; t1.left = mergeTrees(t1.left, t2.left); t1.right = mergeTrees(t1.right, t2.right); return t1; };Copy the code

Swipe questions and punch out records

Here is the previous swipe card records, you can have a look, if you have any different views and views or feel what is wrong, welcome to leave a message in the comment area! 🙏 🙏 🙏

[LeetCode0303 topic area and retrieval – array immutable] | punch brush

[LeetCode1200. Minimum absolute difference] | punch brush

[LeetCode0304 topic 2 d area and retrieval – matrix immutable] | punch brush

[LeetCode11 topic containers of most water] | punch brush

[LeetCode0338 topic bit count] | punch brush

[LeetCode209 topic length minimum subarray] | punch brush

[LeetCode236 topic in recent common ancestor of binary tree] | punch brush

[LeetCode141 topic circular linked list] | punch brush

[LeetCode53 topic most architectural sequence and] | punch brush

[LeetCode48 topic rotating images] | punch brush

[LeetCode155 topic minimum stack] | punch brush

[LeetCode1124 problem well, the longest period of a] | punch brush

[LeetCode274 problem H index] | punch brush

[LeetCode367 problem effective completely square number] | punch brush

[LeetCode1047 problem delete all adjacent duplicates of the string] | punch brush

[LeetCode160 topic cross linked list] | punch brush

[LeetCode1438 topic absolute difference does not exceed the limit of the longest continuous subarray] | punch brush

[LeetCode434 problem the number of words in a string] | punch brush

[LeetCode75 topic classification of color] | punch brush

[LeetCode513 problem to find the value of the trees left] | punch brush

[LeetCode94 title sequence in the binary tree traversal] | punch brush

conclusion

Come on! HXDM!!!!!! 💪 💪 💪

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign