[剑指offer]－二叉树－未实现－树的子结构

NowCoder: 树的子结构-LintCode: 245. 子树

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * 树的子结构
     *     １．前序遍历二叉树T1, 查找与T2的根节点值相同的节点
     *     ２．以该节点为根节点, 判断子树与T2是否相同
     *
     * @param T1, T2: The roots of binary tree.
     * @return: True if T2 is a subtree of T1, or false.
     */
    public boolean isSubtree(TreeNode T1, TreeNode T2) {
        if (T2 == null) return true;
        if (T1 == null) return false;

        // T1包含T2,　直接返回true
        if (isEqual(T1, T2)) return true;

        // T1不包含T2, 判断左右子树是否与该节点相同
        if (isSubtree(T1.left, T2) || isSubtree(T1.right, T2)) return true;

        return false;
    }

    /**
     * 递归比较两棵树左右节点值是否相同
     *
     * @param T1
     * @param T2
     * @return
     */
    public static boolean isEqual(TreeNode T1, TreeNode T2) {
        if (T1 == null || T2 == null) return T1 == T2;
        if (T1.val != T2.val) return false;

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