题解 | #树的子结构#

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/

// 时间复杂度：O（n^2）, 空间复杂度：O（n）
public class Solution {
	// 使用一个辅助函数，同时前序遍历两个子树
    public boolean fororder(TreeNode root1,TreeNode root2){
        // 此处是辅助函数的递归终止条件，判断首层输入节点为空的条件在主函数中
        // 由于是检测root1对root2的包含关系，当root2遍历到最底层时，无论root1是否到达最底层，都返回true
        if (root2 == null)
            return true;
        // root1若单独到达null，则返回false
        if (root1 == null)
            return false;
        // 两者值不同，返回false
        if (root1.val != root2.val)
            return false;
        // 递归：所有的子树都返回true，才返回true
        return fororder(root1.left, root2.left) && fororder(root1.right, root2.right);
    }
    
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root1 == null || root2 == null)
            return false;
        // 当值相等时，使用辅助函数判断是否在当前节点处产生包含关系
        if (root1.val == root2.val && fororder(root1, root2)){
            return true;
        }
        // 值不等则继续遍历
        if (HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2)){
            return true;
        }
        return false;
    }
}