245.Subtree

1.Description(Easy)

You have two every large binary trees:T1, with millions of nodes, andT2, with hundreds of nodes. Create an algorithm to decide ifT2is a subtree ofT1.

Notice

A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

Example

T2 is a subtree of T1 in the following case:

       1                3
      / \              / 
T1 = 2   3      T2 =  4
        /
       4

T2 isn't a subtree of T1 in the following case:

       1               3
      / \               \
T1 = 2   3       T2 =    4
        /
       4

2.Code

判断 T2是否是 T1的子树，首先应该在 T1中找到 T2的根节点，找到根节点后两棵子树必须完全相同。所以整个思路分为两步走：找根节点，判断两棵树是否全等。咋看起来极其简单，但实际实现中还是比较精妙的，尤其是递归的先后顺序及条件与条件或的处理

public boolean isSubtree(TreeNode T1, TreeNode T2) {
        if (T2 == null) return true;
        if (T1 == null) return false;
        //注意这里是T1,T2的equal比较，然后递归left和right
        return isEqual(T1, T2) || isSubtree(T1.left, T2) || isSubtree(T1.right, T2);
    }

    public 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);
    }