剑指 Offer 26. 树的子结构

//树的子结构
public class Offer {

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // A, B为空，则不存在子树
        if(A == null || B == null) {
            return false;
        }
        // dfs(A, B) 当前节点B是否是A的子树，若不是，则同理判断当前节点的孩子节点
        return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    public boolean dfs(TreeNode A, TreeNode B){
        // 比较孩子节点时, B可以为空， 例如[1]是[5,1]的子树
        if(B == null) {
            return true;
        }
        // A为空, B不为空 B一定不是A子树
        if(A == null) {
            return false;
        }
        // 若两个节点的值不同 则B不可能是A的子树 相同则比较两个节点的孩子节点是否相同
        return A.val == B.val && dfs(A.left, B.left) && dfs(A.right, B.right);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}