Subtree

You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

http://www.lintcode.com/en/problem/subtree/

Discussion

通过递归来实现比较简单: T2要么等于T1，要么是T1左子树或者右子树的subtree，这样需要O(h) space。 T1 with millions of nodes，所以这肯定不是最优方案。想节省空间，那当然是用Morris traversal了。

Solution

// Time:  O(m * n), n is number of the nodes in larger tree, m is number of the nodes in smaller one.
// Space: O(h)
class Solution {
public:
    /**
     * @param T1, T2: The roots of binary tree.
     * @return: True if T2 is a subtree of T1, or false.
     */
    bool isSubtree(TreeNode *T1, TreeNode *T2) {
        // write your code here
        if(T2 == NULL) return true;
        if(T1 == NULL) return false;
        //T1 && T2
        return (isEqual(T1, T2) || isSubtree(T1->left, T2) ||
        isSubtree(T1->right, T2));
    }
    bool isEqual(TreeNode *T1, TreeNode *T2) {
        if(T1 == NULL && T2 == NULL) {
            return true;
        }
        if(T1 && T2) {//both not null
            return T1->val == T2->val &&
                   isEqual(T1->left, T2->left) &&
                   isEqual(T1->right, T2->right);
        }
        return false;
    }
};

Morris pre-order traversal. Need to pay attention to the T1->right in the isEqual function, because it may be modified in Morris traversal.

// Time:  O(m * n), n is number of the nodes in larger tree, m is number of the nodes in smaller one.
// Space: O(1)
class Solution {
public:
    /**
     * @param T1, T2: The roots of binary tree.
     * @return: True if T2 is a subtree of T1, or false.
     */
    bool isSubtree(TreeNode *T1, TreeNode *T2) {
        // write your code here
        if(T2 == NULL) return true;
        if(T1 == NULL) return false;
        //T1 && T2
        TreeNode *cur = T1;
        while(cur!=NULL) {
            if(cur->left == NULL) {
                //check cur
                if(isEqual(cur, T2)) 
                    return true;
                cur = cur->right;
            } else { //cur->left != NULL
                TreeNode *tmp = cur->left;
                //find out the precessor of cur in its left subtree
                while(tmp->right != NULL && tmp->right != cur) {
                    tmp = tmp->right;
                }
                if(tmp->right == NULL) {//first time access cur
                    tmp->right = cur;
                    //check cur
                    if(isEqual(cur, T2)) 
                        return true;
                    cur = cur->left;
                } else {//tmp->right == cur, means second time access cur
                    tmp->right = NULL;
                    cur = cur->right;
                }
            }
        }
        return false;
    }
    bool isEqual(TreeNode *T1, TreeNode *T2) {
        if(T1 == NULL && T2 == NULL) {
            return true;
        }
        if(T1 !=NULL && T2 != NULL) {//both not null
            return T1->val == T2->val &&
                   isEqual(T1->left, T2->left)&&
                   isEqual(realRight(T1), T2->right) ;
                   //T1->right may be modifed during the serialization
                   //We need to ignore it for the second time visiting T1
        }
        return false;
    }
    TreeNode *realRight(TreeNode *T) {
        if(T == NULL) return NULL;
        TreeNode *r_right = T->right;
        if(r_right == NULL) return r_right;
        TreeNode *tmp = r_right->left;
        if(tmp == NULL) {
            return r_right;
        }
        while(tmp->right != NULL && tmp->right != r_right) {
            tmp = tmp->right;
        }
        if(tmp->right == r_right) {//second visting r_ight, igore it
            r_right = NULL;
        }
        return r_right;
    }
};