对称二叉树&&二叉树镜像&&树的子结构【递归】

三个题的题目分别见对称二叉树和二叉树的镜像以及树的子结构
对称二叉树：

做递归思考三步：

1.递归函数要做什么？

函数的作用是判断两个数是否镜像输入的是TreeNode left和TreeNode right输出的是true或者false

2.递归的停止条件是什么？

左右结点都为空 -> 到底了长的都一样 -> true一个结点为空的时候另一个结点不为空 -> false左右结点的值不相等 -> false

3.从某层到下一层的关系是什么？

左节点的左子树要和右节点的右子树镜像左节点的右子树要和右节点的左子树镜像

bool recur(TreeNode* leftT,TreeNode* rightT){
    if(leftT==nullptr&&rightT==nullptr) return true;
    if(leftT==nullptr||rightT==nullptr||leftT->val!=rightT->val) return false;
    return recur(leftT->left,rightT->right)&&isS(leftT->right,rightT->left); //递归
}
bool isSymmetric(TreeNode* root) {
    if(root==nullptr) return true;
    return recur(root->left,root->right); //传入左节点和右节点
}

自顶向下进行递归，遍历到每个结点时交换他的左右子树，最终得到的就是镜像树

void recur(TreeNode* root){
    if(root==nullptr) return ;
    swap(root->left,root->right);
    recur(root->left); //向下递归
    recur(root->right);
}
TreeNode* mirrorTree(TreeNode* root) {
    recur(root);
    return root;
}

判断树B是否是树A的子树，需要完成一下两步：

先序遍历树A中的每个结点n_A（对应函数isSubStructure(A, B)）判断树A中以结点n_A为根节点的子树是否包含树B（对应函数recur(A, B)）

判断是否是子树的终止条件：

如果树B为空，说明是子树，返货true如果树A为空，说明不包含B，返回false如果树A的值不等于树B的值，返回false

bool recur(TreeNode* A,TreeNode* B){
    if(B==nullptr) return true;
    if(A==nullptr||A->val!=B->val) return false; //终止条件
    return recur(A->left,B->left)&&recur(A->right,B->right); //递归树A的和树B的左右子树
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
    if(A==nullptr||B==nullptr) return false;
    return recur(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B); //先序遍历
}