Subtree

Find duplicate subtrees

the key to this problem is how to define subtree. Basically, we can serialize the subtree as the following formate:

// 5, #, # (root.val, #, #) # represent the null

besides, we keep one hashmap to record its appearance, and one list to record all those duplicate subtree.

class Solution {
    Map<String, Integer> map;
    List<TreeNode> list;
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        map = new HashMap<>();
        list = new ArrayList<>();

        collect(root);
        return list;
    }

    private String collect(TreeNode root) {
        // idea is that we serialize the bianry tree to a string with format of ...
        if (root == null) return "#";

        String seq = root.val + "," + collect(root.left) + "," + collect(root.right);

        map.put(seq, map.getOrDefault(seq, 0) + 1);
        if (map.get(seq) == 2) {
            list.add(root);
        }
        return seq;
    }
}

time complexity is O(n^2), and space complexity is O(n^2).

or we can use unique identifier to solve this problem.

for a node with left child id of x and right child id of y, (node.val, x, y) uniquely determines the tree. For the null, id is 0;

class Solution {
    int t;
    Map<String, Integer> trees;   // serialize - uid pair
    Map<Integer, Integer> count;  // uid - occurrance pair
    List<TreeNode> ans;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        t = 1;
        trees = new HashMap();
        count = new HashMap();
        ans = new ArrayList();
        lookup(root);
        return ans;
    }

    public int lookup(TreeNode node) {
        if (node == null) return 0;
        String serial = node.val + "," + lookup(node.left) + "," + lookup(node.right);
        int uid = trees.computeIfAbsent(serial, x-> t++);
        count.put(uid, count.getOrDefault(uid, 0) + 1);
        if (count.get(uid) == 2)
            ans.add(node);
        return uid;
    }
}

note: time complexity is O(n) and space complexity is O(n),

map.computeIfAbsent(): If the specified key is not already associated with a value (or is mapped to null), attempts to compute its value using the given mapping function and enters it into this map unless null.

Subtree of another tree

开始想通过遍历T1，找到和T2根节点相等的节点，再比较subtree of T1 和T2是否相等。没有考虑到如果T1中存在多个与T2根节点相等的节点(可能只是node.val相等)，那结果就不能确定了。按上一题判断两棵树identical的思路，在递归基础上，再加一层递归，目的是用T2和T1的each subtree比较。

public class Solution {
    public boolean isSubtree(TreeNode T1, TreeNode T2) {
        if (T2 == null) {
            return true;
        }

        if (T1 == null) {
            return false;
        }

        if (isEqual(T1, T2)) {
            return true;
        }

        if (isSubtree(T1.left, T2) || isSubtree(T1.right, T2)) {
            return true;
        }
        return false;
    }

    private boolean isEqual(TreeNode T1, TreeNode T2) {
        if (T1 == null && T2 == null) return true;
        if (T1 == null || T2 == null) return false;

        if (T1.val != T2.val) {
            return false;
        }

        return isEqual(T1.left, T2.left) && isEqual(T1.right, T2.right);
    }
}

12/14复习注，写的时候要多考虑edge case，有了edge case再写递归出口能让逻辑更严密。

12/30复习，双层dfs。比较的是T2和T1的任一个subtree(包括T1)，要完全identical，有一个正确就行。同时，第二个出口也是主函数traversal的出口。

2/16 时间复杂度，worst case是用Tree2和Tree1的每个节点比较，如果T1节点数为m，T2是n，总共O(m*n)。