题目地址

思路

1. 判断子结构，也就是说可能存三种情况

• 完全和树相同
• 和树的右子树相同
• 和树的左子树相同

2. 递归判断

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    // 递归判断
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        // 搜索判断当前节点是否存在子结构，然后递归左分支，右分支
        return preScan(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

    // 先序遍历判断是否相等
    public boolean preScan(TreeNode A, TreeNode B) {
        if (B == null) return true;
        // 先序遍历相等
        if (A == null || A.val != B.val) return false;
        if (!preScan(A.left,B.left)) return false;
        if (!preScan(A.right,B.right)) return false;
        return true;
    }
}

Q.E.D.