Flip The Tree!!!!

-
Fun problem: https://leetcode.com/problems/flip-equivalent-binary-trees/description/

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.
A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.
Write a function that determines whether two binary trees are flip equivalent.  The trees are given by root nodes root1 and root2.

Example 1:
Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explanation: We flipped at nodes with values 1, 3, and 5.
Flipped Trees Diagram

Note:
  1. Each tree will have at most 100 nodes.
  2. Each value in each tree will be a unique integer in the range [0, 99].
It is actually pretty simple (recursively), 3-lines, cheers, ACC.


public class Solution
{
public bool FlipEquiv(TreeNode root1, TreeNode root2)
{
if (root1 == null && root2 == null) return true;
if (root1 == null || root2 == null || root1.val != root2.val) return false;
return (FlipEquiv(root1.left, root2.left) && FlipEquiv(root1.right, root2.right)) ||
  (FlipEquiv(root1.left, root2.right) && FlipEquiv(root1.right, root2.left));
}
}

Comments

  1. TarasFebruary 6, 2019 at 7:03 PM

    Great minds think alike )):

    class Solution:
    def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:
    if root1 is root2:
    return True
    if root1 is None or root2 is None or root1.val != root2.val:
    return False
    return (
    self.flipEquiv(root1.left, root2.left)
    and self.flipEquiv(root1.right, root2.right)
    ) or (
    self.flipEquiv(root1.left, root2.right)
    and self.flipEquiv(root1.right, root2.left)
    )

    https://gist.github.com/ttsugriy/2e241cc61a2c05224b52c7dc9c139e45

    Interestingly Python keeps beating C# in CPU and memory usage :) (36ms and 6.5MB of RAM)

    ReplyDelete
  2. Boris VasilenkoFebruary 7, 2019 at 8:52 AM

    I will learn Python 🐍

    ReplyDelete
    Replies
    1. TarasFebruary 7, 2019 at 10:15 AM

      haha, I prefer strongly typed languages but Python is definitely a language of choice for ML these days. It's also a great choice for interviews because it's pretty much pseudocode :)

      Delete

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