Merging Binary Trees
Given two binary trees node0 and node1, return a merge of the two trees where each value is equal to the sum of the values of the corresponding nodes of the input trees. If only one input tree has a node in a given position, the corresponding node in the new tree should match that input node.
Constraints
n ≤ 100,000wherenis the number of nodes innode0m ≤ 100,000wheremis the number of nodes innode1
https://binarysearch.com/problems/Merging-Binary-Trees
ExamplesPermalink
Example 1Permalink
Input
- node0 =
- node1 =
Output
- answer =
Example 2Permalink
Input
- node0 =
- node1 =
Output
- answer =
SolutionPermalink
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * class Tree { | |
| * public: | |
| * int val; | |
| * Tree *left; | |
| * Tree *right; | |
| * }; | |
| */ | |
| Tree *solve(Tree *node0, Tree *node1) | |
| { | |
| if (!node0 || !node1) | |
| { | |
| // no need to merge | |
| return node0 ? node0 : node1; | |
| } | |
| else | |
| { | |
| // merge | |
| node0->val += node1->val; | |
| node0->left = solve(node0->left, node1->left); | |
| node0->right = solve(node0->right, node1->right); | |
| return node0; | |
| } | |
| } |
Leave a comment