[数据结构与算法]OJ题目2--嵌套形式的递归

所谓嵌套形式的递归，按照我的理解就是递归的形式比较复杂，不是简单的一句话能说清楚的，这是就需要两层递归进行嵌套，以达到目的。比如计算一个二叉树中有几个节点的问题，求解这个问题的根本逻辑就是一个二叉树的节点个数等于根节点本身加上根节点的左子树中的节点树和根节点右子树中的节点数。依此类推，直到计算到根节点处为止（判断的标准是计算完以叶子节点作为根节点的那次递归之后，其左右孩子节点必然为空，因此节点为空也就成为了结束条件）。上述这个问题的简单逻辑当然可以通过一次递归来实现。但是许多递归问题的逻辑并非总是这么简单，整个问题的求解不能通过一句话反复执行来实现，这是就需要采用嵌套形式的递归。比如判断一个二叉树是否为对称二叉树，当最开始从根节点出发时，当然要比较其左右孩子节点是否相同，但是当这一次比较结束后，后面的比较就不能通过执行这句比较左右孩子来实现了，因为这是如果比较左右孩子各自的左右孩子是否相同时，整个程序就会显得不伦不类（当然如果比较该二叉树是不是单值二叉树时，采用这种方法是正确的）。这时的情况就是前面所说的不能用简单的一句话反复实现来完成计算的情况，这是就需要采用嵌套形式的递归。

1，判断一个二叉树是否为对称二叉树。

101. 对称二叉树 - 力扣（LeetCode） (leetcode-cn.com)

通过两层递归的嵌套，就可以实现对右孩子节点的左孩子节点和左孩子节点的右孩子节点相比较的效果。依此类推，右孩子节点的左孩子节点的左孩子节点和左孩子节点的右孩子节点的右孩子节点相比较，无论怎样比较，相比较的两个节点，判断该节点身份的“左”和“右”永远都是相反的，这就能保证被比较的两个节点关于二叉树的对称轴对称。当然，嵌套递归的结束条件和普通递归相同，都是当计算到二叉树尽头或者发现两个在对称位置的节点的值不相等时，才会结束，否则就会一直计算下去。

bool ist(struct TreeNode*root1,struct TreeNode*root2)
{
    if(root1==NULL&&root2==NULL)
    {
        return true;
    }
    if(root1==NULL||root2==NULL)
    {
        return false;
    }
    if(root1->val!=root2->val)
    {
        return false;
    }
    return ist(root1->left,root2->right)&&ist(root1->right,root2->left);
}
bool isSymmetric(struct TreeNode* root)
{
    if(root==NULL)
    {
        return true;
    }
    return ist(root->left,root->right);
}

2，判断一个树是否是另一个树的子树。

572. 另一棵树的子树 - 力扣（LeetCode） (leetcode-cn.com)

判断一个树是否是另一个树的子树，需要将较大树中的每一个节点都拿出来和小树做比较，如果不符合要求，则拿出该节点的左右孩子节点分别和小树做比较。但是要比较的是树，不是简单的节点，如果是简答的节点，那就和寻找二叉树中值为x的节点没有任何区别。因此，本题的逻辑仍然比用一句话反复实现的递归调用的逻辑要复杂，因此需要使用嵌套递归。多出来的递归主要用来比较两个二叉树是否相等（这一步操作在寻找二叉树中值为x的节点的问题中一个等号就能解决，但比较两个二叉树不可能通过一个等号来解决，这也就是解决本题需要用嵌套递归的核心所在）

bool isSameTree(struct TreeNode*q1,struct TreeNode*q2)
{
    if(q1==NULL&&q2==NULL) //当两个节点都为空时，由于这里的q1，q2本质上都是下面的递归中得来的，所以实际上q1,q2是一个节点的左右孩子节点，当一个节点的左右孩子节点都为空时，说明该节点已经是叶子节点了，当一直比较到了叶子节点时，说明两个树相同
    {
        return true;
    }
    if(q1==NULL||q2==NULL) //第一和第二个if是递归中经典的两个if的结构
    {
        return false;
    }
    if(q1->val==q2->val)
    {
        return isSameTree(q1->left,q2->left)&&isSameTree(q1->right,q2->right); //这个递归的函数本质上是比较两个节点是否相同，只不过组合起来就实现了比较两个树是否相同的效果
    }
    else
    {
        return false;
    }
}
bool isSubtree(struct TreeNode* s, struct TreeNode* t) 
{
    if(s==NULL) //当s节点为空时，说明一直比较到了树的尽头也没找到符合条件的子树，所以要返回false
    {
        return false;
    }
    if(isSameTree(s,t)) //当以s节点和t节点为根节点的两个树相同时，说明我找到了符合条件的子树
    {
        return true;
    }
    Else//既不能确定成功，又不能确定失败，就要继续向下比较，注意这里要用或的逻辑，因为只要有以一个节点为根节点的树与待比较的树相等，就可以得出结论，因此要用或逻辑
    {
        return isSubtree(s->right,t)||isSubtree(s->left,t);
    }
}

相比之下，可以比较一下上面所说的寻找二叉树中值为x的节点问题的代码：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* leftRet = BinaryTreeFind(root->left, x);
	if (leftRet)
		return leftRet;
	BTNode* rightRet = BinaryTreeFind(root->right, x);
	if (rightRet)
		return rightRet;
	return NULL;
}