/**
 * 剑指 Offer 26. 树的子结构
 * https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/
 * */
public class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        if (isEquals(A, B)) {
            return true;
        }
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    public boolean isEquals(TreeNode a, TreeNode b) {
        // 子树已遍历完
        if (b == null) {
            return true;
        }
        // 子树未完但主树已完
        if (a == null) {
            return false;
        }
        if (a.val != b.val) {
            return false;
        }
        return isEquals(a.left, b.left) && isEquals(a.right, b.right);
    }
}