Daily LeetCode #11

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

This is a backtrace problem. We use recursion to check if all subtrees are Flip Equivalent.

Steps:

• determine the base cases
• if both nodes are null, they are flip equivalent
• if one node is null and the other is not null, not flip equiv
• if both nodes are not null, but with different vals, not flip equiv
• do recursion
• for each subtree, either after flip left subtree equals to right subtree or left subtree equals to right subtree without flip should lead to true

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
      // Base case
      if(root1 == null && root2 == null) {
        return true;
      }

      // other base cases
      if(root1 == null && root2 != null || root1 != null && root2 == null || root1.val != root2.val) {
        return false;
       }

       return flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left) || flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);
    }
}

Time Complexity: O(n)

Space Complexity: O(n)

https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/description/?envType=daily-question&envId=2024-10-25

Use sort to put father folders before sub-folders.

Steps:

• sort the input folder
• add first string of folder into list, since it must be a father folder
• iterate strings in folder, check if it is a sub-folder
• if is a sub-folder, skip
• if not a sub-folder, add into list

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        List<String> res = new ArrayList<>();
        // father folders will be before subfolders
        Arrays.sort(folder);

        // the first one must be a father folder
        res.add(folder[0]);

        for(int i = 1; i < folder.length; i++) {
            // check subfolder
            String fatherFolder = res.get(res.size() - 1);
            String curr = folder[i];

            // ignore subfolders, add father folders
            if(isSub(curr, fatherFolder)) {
                continue;
            } else {
                res.add(curr);
            }
        }

        return res;
    }

    public Boolean isSub(String s, String f) {
        // subfolder s must be longer than father folder
        if (s.length() <= f.length()) {
            return false;
        }
        
        // to make father folder full directory
        f += '/';

        // check if beginning of subfolder is equal to father folder
        if (s.substring(0, f.length()).equals(f)) {
            return true;
        }
        
        return false;
    }
}

Notes:

• use Array.sort(array) to sort array
• use Collections.sort(list) to sort list
• need to check f + '/', otherwise cannot correctly determine a/b and a/bc (not sub-folder)

Time Complexity: O(mlogn + mn)

[sort is O(mlogn), isSub is O(m), use isSub n times, so O(mn)]

[n is number of strings in folder, m is length of string]

Space Complexity: O(n)