递归算法：二叉树遍历的核心实现

三、另一棵树的子树

1. 目标特征描述

判断一棵树是否是另一棵树的子树。

2. 目标实现示例

（此处省略具体图示）

3. 算法思路

遍历主树的每个节点，以该节点为根的子树是否与目标树相同。利用前面实现的 isSameTree 接口进行判断。

3.1 具体代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct TreeNode TreeNode;

bool isSametree(TreeNode* p, TreeNode* q) {
    // 第 1 种情况，两个树都为空
    if (p == NULL && q == NULL) {
        return true;
    }
    // 第 2 种情况，其中 1 个根节点为空
    if (p == NULL || q == NULL) {
        return false;
    }
    // 第 3 种情况，2 个根节点存在，但是数值不相同
    if (p->val != q->val) {
        return false;
    }
    // 数值相同，向下进行调用函数判断子树
    return isSametree(p->left, q->left) && isSametree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if (root == NULL) {
        return false;
    }
    // 调用判断最开始时根节点是否匹配
    if (isSametree(root, subRoot)) {
        return true;
    }
    // 根节点不匹配，向下递归调用
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

四、对称二叉树

1. 目标特征描述

判断一个二叉树是否是对称的，即它的左子树和右子树互为镜像。

2. 目标实现示例

（此处省略具体图示）

3. 算法思路

若根节点为空，返回 true。否则比较根节点的左子树和右子树是否对称。对称的判断逻辑类似于判断两棵树是否相同，但需要交叉比较：左子树的左节点与右子树的右节点比较，左子树的右节点与右子树的左节点比较。

3.1 具体代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct TreeNode TreeNode;

bool isSametree(TreeNode* p, TreeNode* q) {
    // 根节点都为空
    if (p == NULL && q == NULL) {
        return true;
    }
    // 一个根节点为空
    if (p == NULL || q == NULL) {
        return false;
    }
    // 不为空，但是数值不同
    if (p->val != q->val) {
        return false;
    }
    // 以上均不满足，代表这两个节点相同，遍历子树继续判断
    return isSametree(p->left, q->right) && isSametree(p->right, q->left);
}

bool isSymmetric(struct TreeNode* root) {
    // 树为空
    if (root == NULL) {
        return true;
    }
    // 树不为空，将左右子树进行对比，看结构是否对称
    if (isSametree(root->left, root->right)) {
        return true;
    }
    return false;
}

总结

本文通过 C 语言实现了四种基于递归的二叉树操作。核心在于理解递归的终止条件与递推关系。掌握这些基础模式有助于解决更复杂的图论与动态规划问题。