树的子结构_JAVA_较难

• 一个方法负责寻找A是否是B的子结构，一个方法负责匹配A是否是以B节点开始的子结构
• 第一个方法：看当前节点A是否是以B节点开始的子结构，否则向B的左右孩子去寻找
• 第二个方法：看当前节点A是否和B相等，且他们的左右孩子也完美匹配

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        // 两者均不能为空
        if(root2 == null || root1 == null) {
            return false;
        }
        // 与当前节点匹配，否则往左孩子，右孩子寻找
        return findSubtree(root1, root2) || HasSubtree(root1.right, root2) || HasSubtree(root1.left, root2);

    }

    // 匹配是否是子结构的方法
    public boolean findSubtree(TreeNode root1,TreeNode root2) {
        // root2为空则说明以上都符合
        if(root2 == null) {
            return true;
        }
        // root1为空且root2不为空则说明不匹配
        if(root1 == null) {
            return false;
        }
        // 当前节点匹配且孩子也匹配
        return root2.val == root1.val && findSubtree(root1.left, root2.left) && findSubtree(root1.right, root2.right);
    }
}