二叉树相关算法实现：判断子树与单值二叉树- 一、判断一棵树是否为另一棵树的子树  

（一）核心思路
 

要判断  root  树中是否包含  subRoot  树作为子树，可采用递归的方法。首先处理边界情况，若  subRoot  为空，说明空树是任何树的子树，返回  true ；若  root  为空且  subRoot  不为空，则  subRoot  不可能是  root  的子树，返回  false 。然后比较两棵树的根节点值，若不相等，在  root  的左子树和右子树中分别递归查找  subRoot ；若相等，进一步判断以该节点为根的子树是否与  subRoot  完全相同，可借助辅助函数  isSameTree  来实现。
 

（二）代码实现
 

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

// 辅助函数，判断两棵树是否完全相同
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL) {
        return true;
    }
    if (p == NULL || q == NULL) {
        return false;
    }
    return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if (subRoot == NULL) {
        return true;
    }
    if (root == NULL && subRoot!= NULL) {
        return false;
    }
    if (root->val!= subRoot->val) {
        // 用 || 分别在左右子树中查找
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    } else {
        // 判断以当前节点为根的子树和subRoot是否相同
        return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
}
 

 
（三）注意要点
 

1. 边界条件处理：在  isSubtree  和  isSameTree  函数中，都要先对空指针情况进行判断，这是递归算法的基础，避免出现空指针引用错误。
 
2. 递归逻辑：在  isSubtree  中，当根节点值不相等时，使用逻辑或  ||  分别在左右子树中查找；当根节点值相等时，要同时考虑当前子树是否相同以及继续在左右子树中查找的情况。 isSameTree  中，只有当当前节点值相等且左右子树都相同时，两棵树才相同。