Leaf-Similar Trees, by LeetCode

-
From LeetCode: https://leetcode.com/problems/leaf-similar-trees/description/

Consider all the leaves of a binary tree.  From left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Nothing really hard about this problem: do a pre-order DFS and add the leaves to a list of integer. Compare the two lists from both the roots. That's it. Code is below, cheers, Boris.
 public class Solution
 {
  public bool LeafSimilar(TreeNode root1, TreeNode root2)
  {
   LinkedList l1 = new LinkedList();
   LinkedList l2 = new LinkedList();
   GetLeafValues(root1, l1);
   GetLeafValues(root2, l2);
   return CheckSimilarList(l1, l2);
  }

  private void GetLeafValues(TreeNode root, LinkedList list)
  {
   if (root == null) return;
   if (root.left == null && root.right == null) list.AddLast(root.val);
   GetLeafValues(root.left, list);
   GetLeafValues(root.right, list);
  }

  private bool CheckSimilarList(LinkedList l1, LinkedList l2)
  {
   if (l1 == null && l2 == null) return true;
   if (l1 == null || l2 == null) return false;
   if (l1.Count != l2.Count) return false;

   for (int i = 0; i < l1.Count; i++)
    if (l1.ElementAt(i) != l2.ElementAt(i)) return false;

   return true;
  }
 }

Comments

  1. TarasNovember 25, 2018 at 7:54 PM

    Nice idiomatic recursive solution! But is it possible to do it faster? Well, we don't really need to perform a complete in-order traversal and use so much extra memory. What we can do instead is to perform parallel iterative in-order traversals of both trees at the same time and for each pair of leaves check if they have same values. C++ code below does the trick in 0ms and beats 100% of other submissions :)

    class Solution {
    public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
    if (root1 == root2) return true;
    if (root1 == nullptr || root2 == nullptr) return false;
    stack s1; s1.push(root1);
    stack s2; s2.push(root2);
    while (!s1.empty() && !s2.empty()) {
    auto node1 = s1.top(); s1.pop();
    while (node1->left || node1->right) {
    if (node1->left) {
    if (node1->right) s1.push(node1->right);
    node1 = node1->left;
    } else {
    node1 = node1->right;
    }
    }
    auto node2 = s2.top(); s2.pop();
    while (node2->left || node2->right) {
    if (node2->left) {
    if (node2->right) s2.push(node2->right);
    node2 = node2->left;
    } else {
    node2 = node2->right;
    }
    }
    if (node1->val != node2->val) return false;
    }
    return s1.empty() && s2.empty();
    }
    };

    I've also posted a more readable paste on LeetCode - https://leetcode.com/problems/leaf-similar-trees/discuss/198179/0ms-parallel-iterative-in-order-traversals-in-C%2B%2B

    Cheers,
    Taras

    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