题解 | #NC98 判断t1树有无与t2树完全相同的子树#

import java.util.*;

public class Solution {
    public boolean isContains (TreeNode root1, TreeNode root2) {
        // 预处理
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        // 在t1树中寻找值等于root2.val的结点
        TreeNode sameNode = getSameNode(root1, root2.val);
        // 判断两树是否相等
        return isSameTree(sameNode, root2);
    }

    // 判断两树是否相同
    public static boolean isSameTree (TreeNode root1, TreeNode root2) {
        // 预处理
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        // 判断根节点是否相同
        if (root1.val != root2.val) {
            return false;
        } else {
            // 递归比较其左右子树
            return isSameTree(root1.left,root2.left) && isSameTree(root1.right,root2.right);
        }
    }

    public static TreeNode getSameNode(TreeNode root, int val) {
        // 预处理
        if (root == null) return null;
        // 检查根结点
        if (root.val == val) {
            return root;
        } else {
            // 遍历查找其左右子树
            TreeNode leftNode = getSameNode(root.left, val);
            TreeNode rightNode = getSameNode(root.right, val);
            // 判断查找结果
            if (leftNode != null) return leftNode;
            if (rightNode != null) return rightNode;
        }
        // 查找失败
        return null;
    }
}