Merge Two Binary Trees, by LeetCode

-
Late night problem: https://leetcode.com/problems/merge-two-binary-trees/description/

Given 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.
You 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.
Example 1:
Input: 
 Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
      3
     / \
    4   5
   / \   \ 
  5   4   7

Note: The merging process must start from the root nodes of both trees.

The solution is to recursively do exactly what the description says: if both exist, add them up. Otherwise, return the one that does not exist. Code is below, cheers, Boris.


public class Solution
{
 public TreeNode MergeTrees(TreeNode t1, TreeNode t2)
 {
  if (t1 == null && t2 == null) return null;
  if (t1 == null)
  {
   TreeNode retVal = new TreeNode(t2.val);
   retVal.left = MergeTrees(t1, t2.left);
   retVal.right = MergeTrees(t1, t2.right);
   return retVal;
  }
  else if (t2 == null)
  {
   TreeNode retVal = new TreeNode(t1.val);
   retVal.left = MergeTrees(t1.left, t2);
   retVal.right = MergeTrees(t1.right, t2);
   return retVal;
  }
  else
  {
   TreeNode retVal = new TreeNode(t1.val + t2.val);
   retVal.left = MergeTrees(t1.left, t2.left);
   retVal.right = MergeTrees(t1.right, t2.right);
   return retVal;
  }
 }
}

Comments

  1. TarasDecember 22, 2018 at 9:36 PM

    I absolutely love these recursive problems! I've decided to reuse as much of existing trees as possible, but asymptotically both time and space complexity is the same:

    class Solution {
    public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
    if (t1 == nullptr && t2 == nullptr) return nullptr;
    if (t1 == nullptr) return t2;
    if (t2 == nullptr) return t1;
    auto newTree = new TreeNode(t1->val + t2->val);
    newTree->left = mergeTrees(t1->left, t2->left);
    newTree->right = mergeTrees(t1->right, t2->right);
    return newTree;
    }
    };

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more