二叉树递归例题分析

二叉树讲解了二叉树的基本知识，这一篇结合例题重点谈一谈递归解决二叉树问题。

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。约定空树不是任意一个树的子结构。B是A的子结构， 即 A中有出现和B相同的结构和节点值。

简单粗暴的解决方案是，先对A进行整体遍历，找出与B树root值相等的节点，再对这些节点逐一判断是否含有B树。那么是否可以在遍历A的时候，同时判断是否含有B树呢？

其实，对于A中的每个节点，我们有必要考虑如下三种状态

• 以该节点为根的子树包含B
• 该节点的左子树包含B
• 该节点的右子树包含B

只要有一条成立，那么B就是A的子结构。所以在递归中的每一层，这三者都是以 || 并列。值得注意的是，对于第一条，其实它就是我们粗暴方案中的第二步

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==nullptr || B==nullptr)
            return false;

        return isIdentical(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }

    bool isIdentical(TreeNode* A, TreeNode* B){
        if(B==nullptr)
            return true;
        
        if(A==nullptr || A->val != B->val)
            return false;

        return isIdentical(A->left,B->left) && isIdentical(A->right,B->right);
    }
};

剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

我们任意画一个3层的二叉树，用它来找规律。不难发现，镜像过程可以如此描述：从根节点开始，交换它的左子树和右子树，然后对它的左节点和右节点再次执行这样的步骤。

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root==nullptr)
            return root;
        
        // exchage
        TreeNode* temp=root->right;
        root->right=root->left;
        root->left=temp;

        mirrorTree(root->left);
        mirrorTree(root->right);

        return root;
    }
};